Google Code Jam 2013 Qualification Round

Code Jamの予選がありました。通過できました。
今年の目標はRound3進出です。

	Small	Large	Large(2)
A	AC	AC	N/A
B	AC	AC	N/A
C	AC	AC	WA
D	AC	WA	N/A

という感じでした。簡単に各問題を振り返ってみます。

A. Tic-Tac-Toe-Tomek

4*4のマス上で四目並べみたいなことをやります。ある局面におけるマスの状態が与えられるので、

• プレイヤーXの勝ち
• プレイヤーOの勝ち
• 引き分け
• ゲーム続行中

のいずれかを判定せよ。

実装するだけです。

B. Lawnmower

芝刈り機で芝生を刈る。芝刈り機は直線にしか進めない。
芝生の状態が与えられるので、芝刈り機を使ってその状態をえることができるかどうか判定せよ。

まず、同じ直線上を何度も刈るのは意味がない。（一番深く刈る設定で１回刈ったのと同じだから）
次に、各ラインを刈る順番に意味があるかどうか考える。互いに平行するラインはどの順序で刈っても結果に影響ないのは自明。互いに交わるラインの順序についても、交差するセルの芝生の高さはがより小さい高さ設定のものになることを考えると、結果に影響がないことが分かる。

よって、まずhorizontalなラインを上から下に矛盾の無いように走査して、そのあとverticalなラインを左から右にかけて矛盾の無いように走査して、それが目的のパターンと合致するかどうか調べればよい。

C. Fair and Square

閉区間[A, B]において、回文数であり、かつ回文数の平方であるような数の個数を求めよ。

SmallとLargeは、あらかじめsqrt(Bのとりうる最大値)までループを回して、回文数の二乗を配列に格納しておけば解けました。

問題は、large-2。よく分からん。Largeでできた配列の中身をprintfしてみると、各桁で使える数は0,1,2と限られてそう。あと二乗したときに桁で繰り上がりがおこるようなものは回文数にはならないので、このあたりをうまく使えば解けそうか・・と思ったけど結局解けませんでした。

D. Treasure

宝箱とそれを開けるために必要な鍵、および、宝箱の中に入っている鍵の情報が与えられる。すべての宝箱を開けるためにはどの順番で開ければよいか求めよ。

初見は、グラフに帰着させてマッチングっぽいことをやるのかなという感じだった。しかしうまく問題をグラフに落とし込むことができず断念。

とりあえずSmallは単純なビットDPで解けそうだったので、解いてみた。
Largeは、もしかしたら、うまく枝刈りすればDFSで解けそうな気がするのではと思ったけど多分無理そうだったので、諦める。