2011-10-08
Google Code Jam Japan 2011
練習問題
A 数珠繋ぎ (Snapper)
- 2進数
- 最後の状態が 2^n - 1 になっているかどうか調べる
- こんな単純なのでいいのか? と思うけど通ってるっぽい。
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/ex_A_snapper.cpp
B 数の集合
- 素数を生成しておく
- union find木にどんどん突っ込む
- rootになっている要素を数える
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/ex_B_set.cpp
C 遊園地
- 次のグループが乗れなくなったら出発
- からっぽの状態から、乗せ始めるグループが既知であれば、ループしているのでまとめて加算
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/ex_C_roller_coaster.cpp
予選
A カードシャッフル
B 最高のコーヒー
- 賞味期限が長い順にソート
- 賞味期限が最も長いもののうち、最も満足度が高いものを消費
- 消費する区間の長さは、対象のコーヒーの在庫終了と、別のコーヒーの賞味期限の終わりの短いほう
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/QR_B_coffee.cpp
C ビット数
- 数NをAとBに分割
- 下から見ていく
- 1だったらそのまま(該当する桁はAが1でBが0)
- 0だったら1引くことにより、AとBが両方1になるので結果が2増える
- Mi_Sawaさんのソースを見て書き直した
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/QR_C_bits.cpp
決勝
A アンテナ修復
- 面積が最大となる並べ方
- smallはnext_permutationでgreedyに通した
- largeは大きい順にソートして、双方向にのびていくように並べた
- 気がつかなかったが、円に近づければよいとのこと
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/A_antenna.cpp
B バクテリアの増殖
- kusanoさんの回答を読んでsmallかつPythonの短さに衝撃を受ける
- smallのみをOpenSSLを使って愚直に実装してみた
- https://github.com/firewood/topcoder/blob/master/gcjj_2011/B_bacteria.cpp
結果
練習→予選→決勝に参加。
予選はAとCのlargeが通って36pt、266位で通過。
決勝はAのみlargeまで通って15pt、195位。
感想
もしかしてTシャツもらえるんだろうか。嬉しい!
練習問題の遊園地はGCJ勉強会でもやった。今回解きなおして、前より少しだけシンプルに書けたかなと思う。
予選はCがそこそこ速く解けたのは良かった。Bは終わった後だいぶかかってしまったがようやく内容を理解した。
決勝はAが通せたのは参加したかいがあった。Bは他の方の解説を読んだがまだ理解できてない。最近ガロアの本とか読んでるがまったく身についてなくて反省。素養がないので地道にやるしかない感じ。
2011-09-28
SRM 516 Div2
Easy (250) NetworkXZeroOne
問題
- oとxだけからなる文字列があり
- 破損して?になっている部分を復元する
方針
- oxoxかxoxoのように交互のものを作ればよい
実装
Medium (500) NetworkXOneTimePad
問題
- 平文と暗号文から鍵の候補を生成する
- 鍵の候補について、暗号文から平文を生成する
- 暗号文の全要素が平文に存在すれば鍵
方針
- 平文と暗号文をXORしたものを鍵候補としてsetに突っ込む
- 各鍵について各暗号文でループしてチェック
実装
Hard (1000) NetworkXMessageRecovery
問題
- 破損した部分文字列から、元の文字列を復元する
- それぞれの文字は1回しか出現しない
- 複数の候補がある場合はアルファベット順
方針
- 文字Xについて、それよりも前にある全ての文字A,B,C...を記憶しておく
- ある文字Yについて、Yよりも前かつ未出力の文字がなければYを出力
実装
結果
oxx 209.00+310.71*0+516.54*0 1117 -> 1076
Easyは、oとxが交互であることが問題文から読み取れず、時間がかかった。
落ち着いて読んだら「任意の偶数個のsubsequenceに含まれる個数が一緒」と書いてあるので必ず交互になる。
Mediumも問題文を斜め読みして、鍵の候補を結果にしたためにsystem test failとなった。
終了後解きなおした。
今回初めてHardのsubmitまでできた。1行breakの位置が違っていたがほぼできてたのでよしとする。
しかしこの一箇所のバグで撃墜されたので、ちゃんと読んでるだなあと思った。
Hardについては、後ろから1文字ずつ処理するとシンプルに書けそうだ。
2011-09-27
SRM 512 Div2
2^nの回。得点も2^n
Easy (256) MarbleDecoration
問題
- 2色だけ使って飾りを作る
- 2に関する問題
実装
Medium (512) MysteriousRestaurant
問題
- 毎日どれかの料理を食べる
- 一度食べた種類は毎週食べなければならない
- 食べるのが途切れたら終了
方針
- x日目について、曜日毎、料理毎にコストの合計を加算
- 各曜日について、最小コストの料理のコストを加算
- 全曜日の合計が予算以内なら日数加算
実装
Hard (1024) DoubleRoshambo
問題
- AshとElshがダブルじゃんけんをする。
- ダブルじゃんけんでは右手と左手の両方でじゃんけんをする。
- 右手も左手も勝った場合は2点、右手が勝って左手があいこなら1点、その他は0点である。
- 順不同でAshとElshの手が与えられるとき、手を並べ替えて、Ashの最高得点を求める。
方針
結果
o-- 243.06 990 -> 999
easyはそこそこ早かった。mediumは実装が間に合わず。
2011-09-25
SRM 511 Div2
だいぶ遅滞
Easy (250) GameOfLifeDivTwo
問題
- ライフゲーム
- Tターン経過後の状態を返す
方針
- 二つの配列をスイッチング
- それぞれのマスで2以上なら'1'
実装
Medium (500) Zoo
問題
- 2種類の動物がいる
- 同じ種類で背が高いやつの数を答える
- 個々の要素がどちらの種類なのかは不明
- 組み合わせの数を答える
方針
- 2種類いる場合は、途中まで同じ数字が2回出てくるので、その重複個数nを数える
- 種類を入れ替えた場合を考慮して2^(n+1)の組み合わせ
- nが総数の1/2のときは2^nになる
実装
Hard (1000) FiveHundredEleven
問題
- カードを交互に出す
- カードが出せないか、出して論理和が511になったら負け
- 最適戦略でどちらが勝つか回答
方針
- とりあえず全探索
実装
結果
ox- 195.58+263.97*0 1003 -> 990
mediumは場合わけができていなくてsystem test fail。まあexampleが通るところまで書けたのはよかった。
hardはとりあえずTLEするコードだけ書いた段階。
あとで解く。解いた
advisoryを読んだ。
- memoryの値が重要で、出した順番は問わない。また、何を出したらよいかもmemoryに依存するので、ターン数とmemoryを保持していれば十分
- 出したら値が変わるカード(すなわち今のmemoryにはないbitを持つカード)を出したときに必勝であるかどうがわかればよい
- そうでない場合は、残り全部が値が変わらないカードなのでカード枚数だけ進めて判定する
2011-09-12
GDD 2011 DevQuiz
ウォームアップクイズ
Google Apps Scriptのクイズがわからなくて全試行してしまった。
Web Game
はじめてのChrome Extension
一度めくったカードを覚えておくようにした。
https://github.com/firewood/topcoder/blob/master/gdd_2011/solver.js
一人ゲーム
- 数値は最大100万なので、21回半分にするとゼロになる
- 最初にn回割ったときに数が5の倍数になるかどうかのテーブルを生成しておく。大きさは21個で済む。
- 割るか除去するかで、なくなるまでBFSでまわす
https://github.com/firewood/topcoder/blob/master/gdd_2011/game.cpp
スライドパズル
さっぱり解き方が分からなかったので、ぐぐって8パズルの解き方とかを読む。
逆方向からも探索するのが良さそうだったので、スタートとゴールからBFSで全探索。
4x4までは解けたので、計算量を減らすために(1)評価値を計算(2)先頭からn個のキューだけ残すことに。
朝まで実行させたら9割方解けたので、残っている問題を閾値を増やして数問解く。
非常に単純な力技だが、最終成績は4961/5000で、予想以上に解くことができた。
評価値はマンハッタン距離ではなく、x^2+y^2としたのが良かったようだ。
https://github.com/firewood/topcoder/blob/master/gdd_2011/puzzle.cpp