2010年度 ICPC 模擬国内予選

初めて参加した．もっとできてもよかったなぁと思うけどまぁ実際にはできなかったのだし実力として認めなければならない．
問題文 http://acm-icpc.aitea.net/index.php?2010%2FPractice%2F%CC%CF%B5%BC%B9%F1%C6%E2%CD%BD%C1%AA%2F%CC%E4%C2%EA%CA%B8%A4%C8%A5%C7%A1%BC%A5%BF%A5%BB%A5%C3%A5%C8
講評 http://acm-icpc.aitea.net/index.php?2010%2FPractice%2F%CC%CF%B5%BC%B9%F1%C6%E2%CD%BD%C1%AA%2F%B9%D6%C9%BE

A 連続する整数の和

まずは A を見る．あれ，解法がわからない．
なんとなく理解して書いてみるもサンプルが通らない…
その後もう一度ちゃんと考え直して微妙に修正．サンプル通った．Accepted．
O(sqrt(N)) の解法だった．
N ≦ 1000 だし O(N^2) で普通にループ回せばよかった．

B ムーンライト牧場

ムーンライト…
問題は全然読んでない．相方が解いてくれた．Accepted．
なんか EPS の値のとり方で WA になることがあるらしいけど，自分のチームのは == で比較して通ったらしい．

C 差分パルス符号変調

DP っぽい．何を表にすればいいんだ．
…わからない．とりあえず次も読んでおこう．
その後，D を考えているうちに相方が解法がわかったということなので解いてもらった．Accepted．

D Mr. リトー郵便局

なんかひたすらこれを考えていた．
最短経路系．全点対間最短経路を求めればよさそう．
しかしそれだと船の状態をどう扱えばいいかわからない．
現在いる街と船のある場所で R 回ダイクストラ？終わるのか？
それで書いてみて入力を食わせてみたところ，意外とすぐ終わった．投げてみるが WA．
出力結果を見てみると 0 が出力されている箇所がある．さすがにこれはおかしい．
よく見たらスタート時に利藤さんは z_1 にいるけど船は街1にいることになっていた．
これを修正して再び走らせて投げる．WA．
しばらく考えてこの方法だとテーブルを更新しきる前に次の目的地についてのダイクストラを始めることになることに気付いた．
時間かかるのを覚悟して走らせる．全然終わる気配がない．でもまぁとりあえず走らせておくことにした．

E 不死の宝石

謎だ… N ≦ 50 だしありうる全ての接線を調べればいいんだろうか．でもそれが本当に最適なのか全然自信がない．
いずれにせよライブラリ必須っぽいのでとりあえず飛ばす．

F 閘門式運河: 上下に動く水面

閘門 ← 読めなかった…*1
問題文もひたすら長い．適当に読み飛ばしてサンプル中心に考えることにする．
特に数学的知識とかは要らず，がんばればできる系の問題っぽい．
時間を等分してシミュレーションはたぶんアウトで，閘門を中心に考えればよさそう．
でも船同士の衝突をどう扱えばいいのかわからない．
さっきの D を走らせつつ相方が解き始めた．
各船の移動は閘門と1つ前の船の移動にしか影響されず，しかも閘門に入る時刻と出る時刻さえ気にすれば衝突を考える必要は無いみたい．ふむ．

実際に動くものが書き上がったころに走らせていた D が終わっていた．約15分くらいかかった．投げてみる．Accepted!!
時計を見るともう17時15分くらいで制限時間内に終わるかどうか微妙だと思いつつすぐに2つ目の入力を食わせる．

結局 F は微妙にバグが取りきれずに提出できないまま．講評を見るに想定外の DP 解法と似てる気がするけど正しかったのかよくわからない．
D のほうも答えを出しきったのが17時32分くらいで残念．まぁそんなに遅いアルゴリズムで書いたのが悪い．海路と陸路でわけて考えて DP とかまず思いつけなかった．
G は一応軽く読んだけど解く気は全くしなかった．

上を見てわかる通り，実際自分で解けた問題が無いに等しく相方頼りだったのが情けない…
あと開始直後から A の解法がすぐにわからなかったこともあり無駄に緊張した．弱すぎる．

*1:実際の運河でこのようなものが使われていることはさすがに知ってた