■ [others]UTPC2009
2009-06-07 12:00-17:00
参加しました。知識だけでは済まない良い問題が多くてとても楽しかったです。
おそれおおくも優勝してしまいました。SRMよりもICPC形式の方が得意なのかなぁ。
懇親会行けなくて残念です。GCJオンサイト(あれば)で会いましょう…!
ログ
- 開始。さすがにサイトが重い
- A開いた
- ハイパーやるだけ問題
- まあ準備運動ですな
- 書いた。サンプル通った。Accept。
- B開いた
- 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開いた
- H~L読んだ
- さすが後半の問題、どれも方針が見えない
- Fに戻った
- 高速化するとしたら、スタートから進めるだけじゃなくてゴールからも戻していく両側探索かなぁ
- …!? あれ、ゴールから見たら一直線に決まっていくんじゃ…?
- なんだ、ゴールから逆向きに進めていくと探索するまでもないのか!!
- 書いた。サンプル通った。Wrong Answer。
- 1箇所処理忘れがあったので修正したらAccept。
- これは簡単に気づかせないよい問題設定だな…
- むずそうなやつらだけ残った
- Iを解いてる人が何人かいるのでIへ
- まだ100分ある! あと1問いけるか
- 数学好き・幾何苦手なのと、すでに解いた人がいるのとでKを選択
- とてもProject Eulerっぽい
- サイズ的に探索は無理
- 数式をいろいろいじる
- 集中力が切れてきた
- ウオッカつえー
- 積の形にして因数でどうのこうのだと思うが…
- おおまかな方針はあってたのか
- 結局どうやっても探索が必要な形から抜け出せなかった
- 終了
- 凍結前のstandingsで1人だけ8問で単独1位だったけど、きっと終盤に誰かが9問通してるよなぁ…と思ってた
- 結局9問はいなかったみたい、というわけで1位ひょえー
- 勝因はこんな所かなぁ
- 後半の方の問題がかなり難しめで、各問題解いてる人が1,2人ずつしかいないような難易度だったので、後半をいくつも通す人がいなかった
- 中盤のあたりは比較的楽だったので、スピード勝負ができた
- ラスベガス組の時差ぼけ(?)