ICPC模擬国内予選&国内予選2014

チーム broken_keyboard で参加していました。*1

模擬国内予選は4完23位で、ちょっとうまくいきすぎたので本番で失敗するんじゃないかと不安になっていました。

本番は4完26位でした。CとDの傾向が過去とかなり違っていて動揺しましたが、ほかの2人の活躍によって、かなり早い段階で4完できました。4完した時点ではEを解くのに十分な時間が残っていたので5完したかったのが本音ですが、とりあえず予選通過の目標は達成できそうなので、今回の反省をアジア地区で活かせるように頑張ります。

2014/07/16 提出時刻のタイムスタンプを追記

チームの構成

私 (@shora_kujira16、B3、AOJは400問弱、青コーダー)
23氏 (Twitter IDは極秘、B4、AOJは350問弱、色無しコーダー)
OUDON氏 (Twitter使ってない、B1、AOJは200問強、緑コーダー)

模擬国内予選

A (14:10 AC)

Aは私が早解きするという作戦でしたので、私が担当しました。

開始前に「全探索全探索全探索…」と念じながら問題ページを開いたら、まさかのシミュレーションで動揺しました。

印刷したりvimrcやMakefileを書いていたら通すまでに10分くらいかかってしまったけど、これは想定内。

B (14:35 AC)

B問題はOUDON氏が担当するという作戦でしたが、「問題の解釈がよく分からない」と言われて私が担当しました。

問題を受け取って読んでみても、確かによく分からない。去年のJAG夏合宿で解いた問題に似ているけど、あの問題は@peryaudo先生にやってもらったんだよなぁ…

なんか下の行から処理していくと簡単そうな感じがしたので実装したら一発で通って拍子抜け。

C (14:56 AC)

「構文解析よく分からないので引き続きよろしく」と言われて私が担当しました。

読んでみると私が得意なパターンの構文解析で、「去年の国内予選Cよりも簡単じゃね？」という感じでAC。

D (16:26 AC)

電車の路線図を題材にした露骨なグラフの問題。今月に入ってから過去問を解き直して練習していたので、私がPCを奪い取って担当しました。

「A社とB社の1dayパスポート(100円)」と「A社とC社の1dayパスポート(200円)」を合成して「A社とB社とC社の1dayパスポート(300円)」を作ったりしたら楽だよね、ということに気づけたのは良かったです。この手の問題は下手にDijkstra法で書くよりもBellman-Ford法で書くほうが楽だということを練習で知っていたので、Bellman-Ford法で書きました。

とりあえず40分くらいで実装できましたが、案の定バグったのでみんなでデバッグすると、23氏が「スタートとゴールの頂点番号を1-originから0-originに直すのを忘れている」というバグを、OUDON氏が「1<<Kと書くべきところを1<<Pを書いている」というバグを見つけてくれて、なんとかAC。

E

空間幾何とか解いたことない… ライブラリも持ってないよ… (ミスリードその1)

これって最低でも「空間内の線分と線分の距離」のライブラリが無いとダメだよね？ (ミスリードその2)

解けそうな雰囲気がないので諦めました。

F

着手できそうな問題がこれしか残らなかったので、みんなで考察。

「包除原理で重複をうまく計算する」というようなありきたりなことしか思い浮かばず、時間切れ。

G

私がCに着手した時点で「観賞用」という報告を受けていたのでスルー。

模擬国内予選まとめ

結局私しかコーディングしてないじゃん！（正直すまんかった）

国内予選

A (16:38 AC)

作戦どおり私が担当しました。「全探索全探索全探索…」と念じていたにも関わらず、解法が思い浮かばなくてかなり焦る。

「なんだ、税抜き価格を全探索するだけか」ということに気づいて愚直に実装したら模擬予選よりも早くにAC。OUDON氏から「早すぎるｗｗ」的なことを言われましたが、終わってしまったものは仕方がない。

B (17:18 AC)

OUDON氏に丸投げしました。バグったそうなので23氏と紙デバッグしてもらっているうちにAC。

C (17:05 AC)

Bと平行で私がコーディングしました。というか、Bよりも先にACしました。

去年のアジア地区予選が終わってから少しずつ幾何の練習をしていて、「どうせ有限点列挙するだけだろー」ということも知っていたのでビル (長方形) の角に太陽の円周が触れる時間の最小値を求めるという方針でコーディングしました。

ビルの角の位置を求める処理が少しゴリ押し感がする書き方をしていたので、バグらないか不安でしたが、あっけなくAC。この時点で1時間たっていなかったので、少し余裕ができました。

D (18:16 AC)

「DPが来るに違いない」と思っていたら、まさかの謎問題が来てかなり動揺しました。

23氏に「N<=20だからO(2^N)が通るよね」という話をされたけど「どういう探索になるかわからないから問題なんだ！！よ！！」と若干キレ気味に返してしまいました。その後「それぞれの文字についてインクリメントするorしない」で候補を列挙してから実際に暗号化してみる、という解法を23氏とOUDON氏に提案されて、粛々と実装するとサンプルが合う。23氏、正直すまんかった。

サンプルが通ったので投げてみるとWA。1分くらい考えると「重複じゃね？」と23氏に提案されて、setに突っ込んでみる (setにする前はpriority_queueに最初5つと最後5つを保存していました)。tailfコマンドでD1.outの出力を眺めながら実行が終わるのを待って、その間に順位表を眺めたりしてAC。

E

23氏が「最初の点と最後の点は遠いほうが明らかにコストが小さくなる」ということを主張してくるが、葉の扱いだけ特別扱いしなければならないあたりで怪しさを感じてしまい、O(N³)の全探索解を書く。1時間以上残っているのだからもうちょっと考察してからかけばよかったのに、いきなりコーディングを始めてしまい、泥沼にはまってしまったので反省しなければならない。

終了3分前にサンプルが通ったけど、O(N³)解がそんなに高速に解けるはずもなく、テストケース1の20/100あたりでContest is Over。