hotpepsiの練習帳

TCO 2013 Round 2B

00:35

Easy (250) FruitTrees

問題

• 一直線な道路に3種類の木を植える
• 種類ごとに植える間隔が指定される
• 異なる種類の間隔が大きくなるように植えていく
• 間隔の最大値を求める

方針

• GCDかな
• GCDの半分ぽいけど、1/3になってる場合もある
• 適当に場合わけして提出
• Failed System Test
• (終了後)
• GCDが全て同じときはGCDの1/3になる。よく考えたら自明
• そうでない場合、最小同士はGCDの半分だけずらす(最小同士の最大値)
• もう一つについては、反対方向に最小のGCDの半分だけずらす
• このとき、GCDが異なる=周期が一致しないので大丈夫っぽい
• https://github.com/firewood/topcoder/blob/master/tco_2013/FruitTrees.cpp

結果

x-- 0pt 498th/1143 rating 1450 -> 1439 (-11)

探索でも解けるようにしておきたい。

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が重かったがいい練習になった。

SRM 576

20:12

Div1 Easy (256) ArcadeManao

問題

• 古いアーケードゲーム
• 水平のプレートがある
• プレート上の水平移動か、梯子でプレート間の垂直移動ができる
• プレート上のどこかにコインがある
• コインを取るのに最小の長さの梯子を求める

方針

• 梯子の長さを0～Xまでのそれぞれで固定して、成立するものが答え
• 変則配点なのでひっかけがありそう
• 到達可能な点同士をunion findでくっつければできる
• 提出
• Passed System Test
• (終了後)
• 普通にDFSで探索すればよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_576/ArcadeManao.cpp

結果

o-- 227th/545 179.18pt rating 1388 -> 1450 (+62)

謎な解き方の割には点数がよかった。割とシンプルに書けた。

SRM 575

18:53

Div1 Easy (250) TheNumberGameDivOne

問題

• 数nをめぐって2人で交互にゲームをする
• 数nから、1とn以外の約数を引くことができる
• 引けなくなったら負け
• 最適手において先手必勝かどうかを求める

方針

• とりあえず愚直な探索を書く
• 1～100くらいダンプしてみる
• なんか不規則な偶奇判定っぽい
• 8,32,128,...が例外
• 理由はわからないけどそのまま書いて提出
• Passed System Test
• (終了後)
• 1または素数でターンが回ってきたら負け
• 偶数でターンが回ってきて、相手を奇数にできるなら勝ち
• 奇数でターンが回ってきたら、相手を奇数にすることはできず、負け
• 2の累乗の場合のみ、偶数でターンが回ってきても相手を奇数にできない
• 2^(2*n)の場合、相手を2または2^(2*n+1)にすることができ、勝ち
• 2^(2*n+1)の場合は負け
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_575/TheNumberGameDivOne.cpp

結果

o-- 443rd/927 143.01pt rating 1325 -> 1388 (+63)

プラス点だけどいまいち。

TCO 2013 Round 2A

19:11

Easy (300) TheLargestString

問題

• 2つの文字列sとtが与えられる
• sとt両方の同じ位置の文字を消去できる
• sとtを連結したもののうち辞書順最大のものを求める

方針

• 貪欲でやってみる
• うまくいかない
• (終了後)
• dp[長さ][何文字目まで使った]でDP
• https://github.com/firewood/topcoder/blob/master/tco_2013/TheLargestString.cpp

結果

• 0pt 438th/1205 rating 1294 -> 1325 (+31)

普通のDPだけど解けず。