Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-09-27

Google Code Jam: Round 2 (2.5hrs)

13:54 | Google Code Jam: Round 2 (2.5hrs) - naoya_t@topcoder を含むブックマーク はてなブックマーク - Google Code Jam: Round 2 (2.5hrs) - naoya_t@topcoder Google Code Jam: Round 2 (2.5hrs) - naoya_t@topcoder のブックマークコメント

配点smalllarge
ACrazy Rows6+16correctTLE
BA Digging Problem9+17--
CStock Charts7+21--
DWatering Plants5+25correctincorrect

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

A. Crazy Rows

  • 各行が何行目より下にあるべきかを見る
  • 全ての行がその要件を満たすように1つずつ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

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

C. Stock Charts

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

総評

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