Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2009-06-08

[]UTPC2009 23:07 はてなブックマーク - UTPC2009 - TopCoderの学習のお時間

2009-06-07 12:00-17:00

http://www.utpc.jp/2009/


参加しました。知識だけでは済まない良い問題が多くてとても楽しかったです。

おそれおおくも優勝してしまいました。SRMよりもICPC形式の方が得意なのかなぁ。


懇親会行けなくて残念です。GCJオンサイト(あれば)で会いましょう…!


ログ

  • 開始。さすがにサイトが重い
  • A開いた
    • ハイパーやるだけ問題
    • まあ準備運動ですな
    • 書いた。サンプル通った。Accept
  • B開いた
    • よくあるやつだ。カタラン数
    • サイズが大きくないので、ゴールからメモ付き深さ優先探索で
    • 書いた。サンプル通った。Accept
  • C開いた
    • 読んだ瞬間分かるnext_permutation
    • サンプルがあらかじめソートされているものばかりなのでソート忘れる人がいそう。ここChallengeポイント(違う)
    • 問題文中にははっきり書いてないけど、引き分けになることもある…?
      • と思ったけど、1-18の合計が奇数だから引き分けにはならんのか
    • 書いた。サンプル通った。Accept
  • D開いた
    • うげーめんどそうな実装問題
    • がんばって書く
    • 奇跡的に一発でサンプル通った。Compile Error…
    • クラス名をMainにするのを忘れていた。ださい
    • 提出し直してAccept
  • E開いた
    • 最初、各段階での状態はくっつける順番に非依存かと思ったけどそうじゃないので、探索だとO(1000!)になって無理か…
    • というわけでマクロな性質を考える
    • 何回繰り上がりが起こるのかは初期状態での数字の和だけで決まるっぽい
    • それと最初の桁数を合わせると、終了まで何ターンかは分かってしまう
    • 書いた。サンプル通った。Accept
  • F開いた
    • シミュレートすれば良いだけ…?
    • スタートから1ステップずつ進めながら、各時点で存在可能な場所を持っておけば良さそう
    • O(50000^2)だけど、状態空間の中で使う箇所はすごく少なそうだからいけるんじゃないの?
    • 書いた。サンプル通った。Time Limit Exceeded。
    • 原因がよく分からなかったのでパス
  • G開いた
    • Fより先にこっち解いてる人が多い
    • これもシミュレーションか
    • 幅優先探索で
    • 一度挨拶した猫の所にもう一回廻ってきたら無限ループ
    • 書いた。サンプル合わない。バグ取った。...(数回繰り返す)...サンプル通った。Accept
  • H~L読んだ
    • さすが後半の問題、どれも方針が見えない
  • Fに戻った
    • 高速化するとしたら、スタートから進めるだけじゃなくてゴールからも戻していく両側探索かなぁ
    • …!? あれ、ゴールから見たら一直線に決まっていくんじゃ…?
    • なんだ、ゴールから逆向きに進めていくと探索するまでもないのか!!
    • 書いた。サンプル通った。Wrong Answer。
    • 1箇所処理忘れがあったので修正したらAccept
    • これは簡単に気づかせないよい問題設定だな…
  • むずそうなやつらだけ残った
  • Iを解いてる人が何人かいるのでIへ
    • ネコがゴールまでの最短距離を行けばいいわけじゃなくて、人がその経路上に着くまでの距離も考えないといけないのか
    • 各点について、「人がそこに着くまでの距離」「ネコがそこに着くまでの距離」「ゴールまでの距離」を出した
    • この3つの距離の和が最小になるとこが答え
      • 幅優先探索を何回もやる必要があった
      • ネコが自力で到達できる範囲を収集するのも幅優先で書いたけど、Union-Find使えればもっと簡単に書けたかな
    • コーナーケース:ネコが自力だけでゴールまで到達できちゃう場合
      • 自分で言うけど、これはよく気づけたな…
    • 書いた。サンプル通った。Accept
  • まだ100分ある! あと1問いけるか
  • 数学好き・幾何苦手なのと、すでに解いた人がいるのとでKを選択
    • とてもProject Eulerっぽい
    • サイズ的に探索は無理
    • 数式をいろいろいじる
    • 集中力が切れてきた
    • ウオッカつえー
    • 積の形にして因数でどうのこうのだと思うが…
      • おおまかな方針はあってたのか
    • 結局どうやっても探索が必要な形から抜け出せなかった
  • 終了
  • 凍結前のstandingsで1人だけ8問で単独1位だったけど、きっと終盤に誰かが9問通してるよなぁ…と思ってた
  • 結局9問はいなかったみたい、というわけで1位ひょえー
  • 勝因はこんな所かなぁ
    • 後半の方の問題がかなり難しめで、各問題解いてる人が1,2人ずつしかいないような難易度だったので、後半をいくつも通す人がいなかった
    • 中盤のあたりは比較的楽だったので、スピード勝負ができた
    • ラスベガス組の時差ぼけ(?)
 |