hotpepsiの練習帳

Google Code Jam 2014 Qualification Round

01:11

Problem A. Magic Trick (6pts)

問題

• 数当て
• 4x4個の数が2セット与えられる
• 観客が数を一つ選び、最初と次の並びの行の場所を答える
• 数が一意かどうか、または観客が嘘をついているかどうかを答える

方針

• 両方の行に含まれる数値を求める
• 0ならうそ、1なら一意、2以上なら失敗
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_A.py

Problem B. Cookie Clicker Alpha (8pts/11pts)

問題

• クッキークリッカー
• 毎秒2個クッキーが焼ける
• F個のクッキーで工場が建てられる
• 工場を建てると毎秒の生産能力がC個増える
• X個のクッキーを焼く最短秒数を求める

方針

• 漸化式かと思ったけど式が作れない
• Cは1以上なので収束するっぽい
• 次の工場を建てたほうが早ければ建てる
• 放置したほうが早いなら放置して終了
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_B.py

Problem C. Minesweeper Master (11pts/24pts)

問題

• マインスイーパー
• R行C列の盤面にM個の爆弾を置く
• 1clickで解けるなら盤面を出力する

方針

• smallは最大25マスなので、全列挙して可能かどうか探索する
• DFSで埋めて判定
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_C_s.cpp

Problem D. Deceitful War

問題

• 重さが全て異なる石を使うゲーム
• 先手が重さを言って石を出す
• 後手が石を出す
• 重いほうが1ポイント得る
• ここまでが普通のゲーム
• チートありのバージョンは、後手の重さが全て既知
• そのうえで、後手にばれない範囲でうそをつく
• 正しい重さを言わなくてもよいが、うそがばれてはいけない
• 普通のルールの最大ポイントと、チートありルールの最大ポイントを求める

方針

• ソートしておく
• チートなしの場合、最大から出しても最小から出しても結果が変わらない気がする
• とりあえず最小から出してシミュレーション
• チートありのとき
• 先手の最小値が後手の最小値より軽いとき、その石でポイントを得ることはないが、後手の最大値より少しだけ軽い値を言うことで、一番軽い石を使って一番重い石を浪費させることができる
• そうでないときは後手の最大値より大きな値を言うことで、後手に一番軽い石を出させて、先手の一番軽い石でポイントを得る
• https://github.com/firewood/topcoder/blob/master/gcj_2014/QR_D.py

結果

毎年の楽しみの一つ目到来。

A small、B small+large、C small、D small+large=66pts 2059th/25462

クッキークリッカー、ナイスすぎる。

うっかり予選が終わる前にコードを公開してしまい、コピペされてた。そのぶんの点数が引かれるだけなら通過はできると思うが気をつけたい。

参加条件読んだら、予選だけは問題について話してもいいらしい。