naoya_t@topcoder

Google Code Jam: Round 2 (2.5hrs)

13:54 |

結果：11点、1768位、TシャツGETならず。

A. Crazy Rows

• 各行が何行目より下にあるべきかを見る
• 全ての行がその要件を満たすように１つずつswap
• (2 1 1 0) → (0 1 1 2)ないし(0 1 2 1), みたいな
• 最小swap回数を得るプログラムを書けばよい
• 書けばよいんだけど
• ごめんなさい
• smallはpriority_queue使って書いたけどこれではlargeは無理だろう
• 残り数分のところで折角なのでlargeデータをダウンロードしてみたけど14番目までしか進まないし

B. A Digging Problem

• ダイクストラで解けると思って書いてたけどサンプル入力で結果が合わない
• digの動作は掘った穴に落ちる動作と別だという事に気づくなどした。
• 心が折れたので後回し
• 他の人達の様子をみつつ、CをスキップしDに着手

D. Watering Plants

• 全植物の相互間距離、というか２つを選んでそれを内包する円の半径を求めてみて、一番大きくなる２つ（リーダーとしようか）を選び、あとの植物はそのどちらかのグループに入るように選ぶ作戦
• どちらに入るかの選択は個々の植物とリーダーを内包する円の半径で決める（←これが駄目かも）
• 最終的なスプリンクラー半径はグループに属する植物とリーダーを内包する円の半径の最大値（←そりゃ駄目だろうな）
• small, largeとも提出。smallは（なぜか）通った

C. Stock Charts

• 最後の５分ぐらいでちらっと見ただけ

総評

• 1768位…せめて３桁行きたかった
• 日本人参加者のRound2戦績(※1点以上)
• 500人というハードルは高い…割とみんな落ちてた
• 足切りラインが28点あたりで、smallを全通しした27点では足りない。largeを最低１つ通さないと勝てないし、１つ通すだけでも遅ければ勝てないという
• もっと沢山の種類の問題に触れ、必要なアルゴリズムの実装に慣れるなどして、思考とコーディングのスピードを上げたい
• でもすごく楽しかった。来年もやるなら出たい