ICPC 2014 Tokyo Regional Contest 参加記

7完でチーム順位6位（大学順位5位）でした。上のチームに中国チームが多いのでまた世界大会参加できるかも？
基本戦略は予選と同様にzerokugi君とn_vip君に読解・解法を丸投げして私が実装するという流れでした。
WFが狙える順位をとるという目標はとりあえず達成できたような気がするものの、Colorful Jumbo Chickenに僅差で負けてしまったのがかなり悔しいので台湾でリベンジしたいですね。

時系列

以下おぼろげな記憶ベースの時系列。もし他の二人の参加記と食い違いがあったらたぶん私の方が間違ってます。
（いつもコンテストが終わるころには最初の方の問題内容を忘れているレベルでコンテスト中のイベントを記憶できない）

A問題

大した量でもない環境設定とテンプレート入力を済ませたらzerokugi君から問題概要と解法（2パターン作って試すだけ）が飛んできたのでサクッと実装。AC (8min)

B問題

A問題通った後にn_vip君から概要を聞く。問題概要を聞いているのか解法を聞いているのかわからないレベルのやるだけ問。制約的にもっと少ないコードでも行けそうだけど変なバグを埋めないようにいつもの再帰下降パーサを書く。AC (16min)

C問題

zerokugi君から解法を聞く。実装してる途中で 7->4, 4->6, 6->5 みたいなパターンやばくない？と聞いたらやばそうという話になって再検討する。問題を再確認すると c_i < d_i なのでやっぱりもともとの解法で問題ないとなって残りの実装。AC (30min)

F問題

気が付いたらFがぼちぼち通されてきているので問題を聞く。解法は全部の辺について除去したときに試せばいいのではという話で書く。（適当に作ったMSTの）すべての辺であることを忘れて「あれ？だめじゃね？」となるもすぐツッコミが入って軌道修正。サンプル通ったので提出。TLE。辺の入力を受けるループをn回しか回していないことに気づく。再提出。またTLE。UnionFindの写経ミス発覚。再提出。AC (63min +2)
今思うとここの誤答がすごくギルティな感じだった……

G問題

zerokugi君から(を+1、)を-1とした数列の累積和の1以下になる点のうちある区間内で最も後にあるものが求まればいけると聞いて遅延評価 Segment Tree でできるよなぁ、となって写経スタート。途中で一度印刷して写経ミスチェックしてもらいつつ残りの実装。サンプル合わないものの区間の+1をつける位置が間違っていてそれを調整をするととりあえず通る。提出。WA。適当にいくつか入力を作ると "() 2" で 1 が返ってきて明らかにだめっぽい。遅延評価 Segment Tree の修正があまりよろしくない感じになっていたので修正すると今の解法には使えなくなってしまい唸っているとzerokugi君が「そこまでできてれば二分探索足せば答えは出せます」と言うので追加。実行時間怪しいかもとのことだけれどもダメだったら考え直そうと言って提出。AC (113min +1)

E問題

HIJKはやばそうという話なのでとりあえずDEの行けそうな方をくださいと相談。n_vip君がEがループ回数1000万くらいで行けそうということなのでそっちを聞く。処理内容聞いてもやばそうな処理は含まれていないので行けるだろうと判断。実装。途中で実装方針の修正を一度入れたものの特に大きなトラブルもなく提出。AC (151min)

D問題

まぁ次に解くべきはDですよね、というわけで解法を聞く。ちょっと細かい式変形が詰まってなかったけどこれは実装する人間がやったほうがよさそうと言って2人にはHIJKの思考に移ってもらうことに。必要な式が一通りそろったので実装するとサンプル2が合わないので計算途中の値をダンプして眺めているとzerokugi君から「（バウンド回数固定なら）45度の時が一番小さい速度で行けるはずなので二分探索の下限は45度でOKです」と言われて修正したらサンプルあったので提出。AC (179min)

H問題

残り2時間で「HIJKどうする？」となる。とりあえずHは気合で実装すれば何とかなりそうと主張。結局Iをzerokugi君が、Jをn_vip君が考えて待ってる間にHを実装する方針に。H問題で最低限必要そうな幾何要素はpipe.txt時代のライブラリに揃っていたのでとりあえずガシガシ写経する。残り30分くらいでとりあえずコンパイルは通る。サンプルでSEGV起こすのでサクッとgdbで修正するものの解が全く合わない。ちょっと残り20分でデバッグしきれる気がしないのとzerokugi君がI思いついたかもと言うのであきらめることに。

I問題

聞いてみても（頭が半ばばててきていたのもあって）解法を理解しきれず、この残り時間で理解+実装をできる自信がなかったので実装もzerokugi君にバトンタッチ。完全にギャラリー会と化して実装を見守る。残念ながら間に合わず。解説を聞いたところ解法は合っていたらしいのできちんと解法をこちらで理解できてれば間に合ったのかもと思うとここも後悔が残る感じに。

反省

ちょっと今回はライブラリ関係の時間ロスが多かったような気がするのでいい加減簡易チェッカくらい導入してみたい気はしますね。
あと終盤の難しい問題でzerokugi君の頭から自分の腕までの伝達が極端に遅くなるのをどうにかしないと……（ほぼ完全に私の頭に原因があるわけですが）

おまけ

帰宅フェーズ失敗（自宅の鍵を紛失）してしまいこれを書いている時点でまだ自宅に到達できていません。というわけでまだ私のICPCは終わっていなかったりします。
関係各所にご迷惑をおかけしてしまい申し訳ないです……