hotpepsiの練習帳

Google Code Jam 2013 Qualification Round

01:38

Problem A. Tic-Tac-Toe-Tomek

問題

• ワイルドカードありの4目並べ
• ゲームの状態を答える

方針

• 縦、横、斜め(×2)で判定
• https://github.com/firewood/topcoder/blob/master/gcj_2013/QR_A.cpp

Problem B. Lawnmower

問題

• 芝の状態が与えられる
• 水平または垂直にまっすぐ芝を刈る
• その状態にできるかどうか答える

方針

• 水平で考える
• 最高の高さmを求めておく
• mより低い場所があったら、垂直で刈った部分として記憶する
• 垂直についても同様
• 刈った高さ未満の場所があるかどうかで判定
• https://github.com/firewood/topcoder/blob/master/gcj_2013/QR_B.cpp

Problem C. Fair and Square

問題

• 回文数を2乗したものが回文数なものを求めたい
• AからBまでの個数を求める
• ↓これらしい
• http://oeis.org/A057136

方針 (small)

• 全探索

方針 (large 1)

• 順列から回文数を作るには、偶数桁なら反転してくっつけて、奇数桁なら中央以外を反転してくっつければいい
• 範囲が10^14までなので、2乗する前の回文数は10^7未満
• 最大でも10^4の列挙から作れる
• https://github.com/firewood/topcoder/blob/master/gcj_2013/QR_C1.py

方針 (large 2)

• わからん
• (終了後)
• tomerunさんのソースを読む
• 数をabcdcbaなどとして筆算してみる
• 桁上がりすると左右対称でなくなり破綻する
• 桁上がりしないことを必要条件にしてみる
• 中央の数値は、2×(a^2＋b^2＋c^2)＋d^2のように、2乗の和になる
• 元々中央の数以外は2倍
• なので、中央の数以外は、2乗の和が4以下である必要がある
• すなわち2が1個以下か1が4個以下(最初の桁を含む)
• 中央の数は0から2まで試す
• そういう数を列挙して、回文数を作って、2乗して判定する
• https://github.com/firewood/topcoder/blob/master/gcj_2013/QR_C2.py

Problem D. Treasure

問題

• 何種類かの錠前がついた宝箱と、いくつかの鍵がある
• 宝箱の中にはいくつかの鍵が入っている
• 全ての宝箱を空けられる順番を求める
• 複数可能なときは、宝箱の番号の辞書順最小

方針 (small)

• 鍵を辺、宝箱を頂点としてBFSで力技
• 経由違い(例えばA->B->CとB->A->C)を同一と見なすよう記憶しておく
• (終了後)
• DFSでよかった
• https://github.com/firewood/topcoder/blob/master/gcj_2013/QR_D.cpp

結果

A + B + C large 1 + D small = 135pt

2乗と回文がつらいので、CはPythonで解いた。回文判定・生成はスライス大活躍。

C large 2が重かったがいい練習になった。