GCJ2013Qualでなんか14位でした。R1進出には無意味だと思いながらも提出したおかげですかね。
ムダに実装量を増やす要素があってうっとうしかったけど、問題自体は割と面白かったので感想を。
Problem A. Tic-Tac-Toe-Tomek
やるだけ
絶対クソゲーだけど今度遊んでみよう。
Problem B. Lawnmower
高さの設定を１ずつ低くしながら刈ってもいい行・列を刈っていって、最終的なmapと完成形が同じかどうかを確かめる。
制約が厳しかったら、全てのセルに「h >= min(同じ行にあるhの最大値, 同じ列にあるhの最大値)」が成り立っていることを調べればいいと考えて O(NM) の解法を選ぶのかな。
Problem C. Fair and Square
とりあえず「f(X) = √X以下の数のうち回文数かつその二乗も回文数であるもの個数」という関数を作ればいい。
「回文数かつその自乗も回文数である」というのは、証明はしてないけどどうやら二乗する時に繰り上がりが起こらなければいいらしい。で、回文数の二乗において最も繰り上がりが起こりやすい桁は二乗後の数の真ん中の桁になります。それはその桁が各桁の二乗の和となっていることから証明できます。
つまり必要な条件は「全ての桁の二乗の和が9以下」となります。あとは「3」というコーナーケースみたいなのに注意しながら適当によくあるDPを書けばいいです。めんどう・・・
Problem D. Treasure
辞書順最小といううるさい制約があるけどとりあえず、「ある状態からクリア可能か」を判定して各ステップで全通り試して最小の物を取っていけばいい。
で、「ある状態からクリア可能か」を判定するためにはシミュレーションをするんですが、その戦略は、
typeXの鍵を使うとき、何回かのステップの後に再びtypeXの鍵を手に入れられるような開け方がある場合それを優先し、無い場合はどれを開けても良い。
という感じです。なぜこれでうまくいくのかを考えると面白いです。とりあえず実験しておきます。(鍵タイプはアルファベットにしてます)
最初に持っている鍵：A 番号：鍵タイプ：入っている鍵 １：A：なし ２：A：B ３：B：A ４：B：B
このときは
Aの鍵を持っていて、２→３と開ければ再びAの鍵が手に入るので２を選ぶ Bの鍵を持っていて、４を開ければ再びBの鍵が手に入るので４を選ぶ Bの鍵を持っていて、再びBの鍵を手に入れることはできないので適当に３を選ぶ Aの鍵を持っていて、再びAの鍵を手に入れることはできないので適当に１を選ぶ
step1では「２→３」と開ける予定でしたが、step2に行った後はそれは関係なくBの鍵を再び手に入れることだけを考えます。再びBの鍵を手に入れられるなら今すぐ３を開ける必要はないのです。要は問題の先送りをし続けるゲームなのです。ちなみに鍵を同時に複数個持っている時の鍵を使う順番はどうでもいいです。
Round3とかでもこの順位ならいいのに・・・w
