2013-04-14
GCJ2013 Qual
Other | | 
最近は完全に引退勢でした。
A
Tic-Tac-Toe が 4x4 になって、Tomek (内輪ネタ...) なる X / O どちらとしても使えるものが最初から盤面に置かれている。盤面を見て勝敗を判定せよ。
やるだけ。
どちらも勝利条件を満たしているときの処理は invalid な盤面はないとのことなので無視して良さげ。
B
縦横1直線に同じ高さに刈れる芝刈り機があるので、与えられた芝の高さが作れるか判定せよ。
やるだけ。
縦横どちらかの方向でそのマスより高い芝がなければ良いので、各行・列の最高を求めておけば簡単。
C Small / Large1
閉区間が与えられるので、x, x^2 が回文となるような x^2 の個数を求めよ。
やるだけ。
x だけ全列挙しておけばよいので高々 10^7 個、あらかじめ求めておいてもよいのでさらに簡単。
C Large2
注: これはまともな解法ではありません。想定解法は他の人の解説を見てください。
実際に数えてみると 39 個しかないので、観察してみた。
すると x には次の規則性があるように見えた。(未証明)
- 1桁のとき
- 1, 2, 3
- 両端
- 1, 2
- 奇数桁のときの真ん中
- 0, 1, 2
- それ以外
- 0, 1
となり、列挙すべき候補がだいぶ減ったように見える。
実際調べてみると 40,000 ちょっとだった。
あとは埋め込みして2分探索。したけれども、ソースコードが大きくなりすぎて弾かれた。そういえばそういうのもあった。覚えていたら形式をもう少し考慮したのに。反則とられるのも嫌だったのでスルー。
Practice は通った。
D Small
箱の鍵がいくつか入った箱が幾つかあるので、全部開けられるような順番を求めよ。複数あるときは辞書順最小で。
Small は小さいので巡回セールスマンで解いた。直前の状態が何だったかを覚えておく必要はないので少し状態は減る。
D Large
マッチングに見えた。よく知らない。
結果
135 で 1205位。
おまけ
毎年 http://www.go-hero.net/ から去年のものを発掘してきてテンプレを作るのも賢くないので自分用にペタリ
