Qualifier for Nationwide Preliminary 2009, SAITAMA

ICPC

埼玉大学の学内予選。結果は3位でした。順位的には満足してますが、Dを通せなかったのが心残りです。

以下、参加記録。
「自分が審判をやったコンテストの参加記録を見るのはとても楽しい」とこないだ知ったので、特に日本のコンテストでは、審判団への感謝を込めて参加記録を書くようにしています。Maximumの人たちがここを見てるかどうかは知りませんが*1。
みんなも参加記録書こうぜ！

コンテスト前夜
  • 懇親会のお誘いが来てた。19時に池袋。無理ゲーのにおいがする。
  • 路線検索してみる。どうやら16時頃に会津を出ればいいらしい。
  • 1時間半で全完したら行くことにしよう。まず無理だけど。
Problem A: Two keyboards
  • 書くだけ。STL使いまくって実装。
  • バグった。やりなれないことはするものじゃない。
  • 怪しげなところを直したらSampleが出てき・・・てない。>>をgetlineに書き直す。
  • Submit, Accepted.
  • 余談ですが、問題文中にでてきたDvorak配列を昔習得しました。
  • 最近ではあまり使ってませんが、結構快適でした。
Problem B: Sum of Consecutive Primes
  • これも書くだけ・・・だけど、やっぱりバグった。
  • 篩をちょっと書き間違えてた。直してSubmit。Accepted.
Problem C: The Fugitive, Once Again
  • ・・・もしかしてそのまんま巡回セールスマン問題？
  • いやいやそんなど真ん中ストレートなはずが。何か駄目なケースがあるんじゃないか？
  • N = 13だから全探索 + 枝刈りのにおいもする。こっちが正解じゃないのか？
  • ・・・。
  • 落ち着いて考えてみよう。
  • 「入力サイズを見るに、ものすごい大量の並行辺がある」
    • -> 絶対に2本以上使えないので、一番重いのだけあればOK。
  • 「『同じ頂点を2度踏めない』って書いてあるけど、普通のTSPのDPだとそれ考慮しないよね」
    • -> それは前処理のWarshall-Floydを省けばいいだけでは？
    • TSP-DPはあれがああなって答えが求まる仕組みだから・・・。
  • やっぱりTSPで良さそうだ。
  • 書いてみた。送ったら通った。
  • このあたりでStandingsを見てみたら、それなりにいい位置にいた。快調快調。
Problem D: Safe Universe Trip
  • Problem Dの D は Dijkstra の D。というわけで愚直に書いてみる。2,700万ノードならどうにかなるだろー。
  • ・・・書けた。けど、手元で走らせてみると落ちたり結果が返ってこなかったり。小手先の改善に走る。
  • よく見たらメモリの確保の時点で落ちてる。絶望的じゃん。早く気づけよ自分。
  • 結構時間を浪費したなと思ってStandingsを見てみたら、まだ誰もDを解いてなくて安心した。やっぱこれ難しいんだ。
  • konakonaさんがEを解いてる。こっち先にやろう。
Problem E: An Easy Homework...?
  • 論理回路のシミュレーション。(ゲート数)*(時間)が全部メモリに乗りそうなので、全部メモしてしまおう。
  • それにしても、世界大会で似たような問題を見かけたなぁ。あれはyukが片付けてくれたので、彼ならこれ瞬殺だろうなぁ。
  • 向かいの席で後輩MがReject食らいまくってるのを眺めながら実装。出来たっと。
  • 入力の取り方を間違えてたので直したらSampleが出てきたのでSubmit。Rumtime Error.
  • 印刷して読んで見るも、原因が分からない。
    • まさか再帰しすぎてスタックオーバーフローなんてことはないだろうし・・・。
  • もっかい問題眺めてみる。・・・あ！配列の長さ足りない！
    • 入力ゲートも論理ゲートもそれぞれ最大256個なので、最大512個だ！
    • 問題文の256という数字に引きずられてた・・・。
  • Resubmit. Accepted!
    • もったいないミスだった・・・。
  • さて、DとFどちらをやろうか。とりあえずFを読んでみよう。
    • ・・・探索か。それも結構大変そうだ。
  • Standingsを見ると一人だけDを解いてる。彼に解けて私に解けない問題などあってはならない。D行くぞD。
Problem D: Safe Universe Trip (Retry)
  • もっと良い方法を考えてみよう。
  • 重要な座標値は始点・終点・トンネルの場所ぐらい。それらの距離を求めてダイクストラすればいけそうだ。
    • 距離の計算はBFS(flood-fillとか言うらしい)で。
  • ひたすら実装しまくる。
    • 書いても書いても終わらない。
    • すごい勢いでスパゲッティが茹だる。
  • やっと出来た・・・。まだ時間に余裕があるし、今日はあまりRejectを食らっていないので、慎重にテストしてみよう。
    • 「妙なケースが見つかる」 -> 「よく見たら入力の書き間違い/ただの勘違い」というループを何回か繰り返す。
  • 大丈夫そうだ。Submit! TLE...
  • この後頑張って高速化してみたけど、やっぱりTLEのままコンテスト終了。4問でした。
Final Standings
  • 3位でした。やったー。
    • 今まで時間差で良い順位を取れたためしが無いので、とても満足です。
  • とは言え、最後にDが解けていれば1位だったと思うと悔やまれます。1位の人、おめでとうございます。
  • 相変わらずkonakonaさんの解き方がおかしい。AをスルーしてBに行ったりとか、Eを30分で解いたりとか。
    • いったい何者なんだろう・・・。
  • Maximumの皆さん、楽しいコンテストをありがとうございました。

*1:そもそも誰がここ見てるのかさっぱり知らない