ICPC Tsukuba 2016 参加記

競プロ ICPC

慶應義塾大学のチーム「Running」として参加し、３位の銅メダルでした。
メダルを取ることが出来たのは初めてで、とても嬉しいです。

時系列順で感想を羅列していきます。

コンテスト前日

つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯を食べた。

プラクティスでは、キーボードの癖の把握とスタックサイズの調査をすることにしていました。
キーボードは重めでびっくりしましたが、打ちやすくとても良かったです。
いつもはMacで⌘→で行末に移動しているので、Endキーを押さないと行末に移動できない環境には少し戸惑いましたがそんなに大きな影響はなかったです。
時間はあと15~30分ほど長いと嬉しいなと感じました。
会場の配線は、人が通る場所に線が、去年より心なしか少なかった気がする？

懇親会は帰りのバスを待つ時間が長くて、寒かったのもあってつらかったです。

ホテルについたら真っ先に大浴場に入った。
それから、peryaudoと近くのショッピングセンター的なところで買い物をした。
レジが半自動ですごかった。
ホテルに帰るときにライトアップされた変な建物を見つけた。
だいたいこういうのってラブホテルとかいうやつなんですが、それにしては大きいなぁと思って調べてみると、近くに保育園があって、教会系の結婚式場なのではという結論になった。納得した。

夜は結局寝れなかった・・・
結構眠気が強かったので寝れそうだと思っていたんですが、２時間ほど浅い睡眠をしたあとに廊下の声とかで起きてしまって、そこからは絶望の時間が始まりました。
なんか今年も１時くらいに暴走族がいたんですが、これIOIやったときにもいたら日本の印象的な意味でアレそう。
結局1~2時間くらいしか寝れなかった。

コンテスト当日

わりと眠かったですが、プリン食べてユンケル飲んで乗り切りました。（去年もそうした）
入場する前にタイピングソフトをやってみたところ、そこまで悪くない速度だったので少しだけ安心しました。
（これが遅かったら脳の回転速度が相当低下しているということで、やばかった）

コンテスト中の動向

うちの体制は、A,B をperyaudoに投げて、その間に先の問題を読んだり解法を考えたりしておくという感じです。
その後は２人に問題を読んでもらって、ライブラリ写してもらったりサンプル図示してもらったり手計算を投げたりとかする感じです。

A

開始直後peryaudoに投げたら一発で通してくれた。

D

Cが簡単だったのでperyaudoに投げてみて、Dからやった。
１回WAを出して直して投げたら、map<vector<int>,int>のせいでTLEしてしまった。

C

ジャッジ待ちの間にperyaudoに聞くと少し自信がなさそうだったので、自分でやることにした。
出力を改行区切りにしてしまって１WA食らった（だめやん）

D2

ハッシュに書き直して投げたけどWA。もうちょっとちゃんとハッシュを組まないといけなかったっぽい。

B

Cやってる間にperyaudoに読んでもらっていたので、やってもらった。１発ACいいぞー。
罠があったっぽいですが、少しのデバッグで乗り切ってたのはさすがっすね。
コーディングしてもらってる間に問題文を聞いたりした。

D3

vector<pair<vector<int>,int>>をsortすることにしたら通った。
TLEでハマるのはかなり泥沼なので、この程度のロスで済んだのはよかった。
ただ、ペナルティを結構食らったので、以降はペナルティをあまり意識しない方針にした。

G

E,Fがパッと見では分からず、順位表見たらGが解かれていたのでGに行く。
はじめsetを書こうとしたけど使わなかった。
細かいバグを何回か埋め込んで、3WA食らった。

E

Iが見た目簡単そうに見えたけど、WAしてるチームがあったしやめといた。
（そのとき考えてた方針は結局計算ミスしてて全然ダメだった）
次にやるものがないなーと思っていたけど、Eは同じ記号を違う文字に割り当てられないのに気づいて、それならただの実装問題やんとなり、これをやることにした。
再帰下降構文解析は頭を使わずに書くだけでいいので楽ですね。
末尾に'$'とかをつけておくと配列外参照とかを防げて楽でした。
（イテレータを正しくインクリメントするのだけは気をつけないといけないけど）
文法が正しいかまで含めて式を評価しないといけない問題だったので少し不安だったけど、１発で通ってびっくりした。

F

Jが解かれていたけど幾何だし、通してた中国チームはなにか類題を見たことがあったっぽい雰囲気を感じたのでやめた。
とりあえずFに取り組んだ。
問題設定がなかなか独特で、どうアプローチすればいいのかに悩んだ。
2-SATっぽい雰囲気のある設定だったけど、全然そんな形にはできなさそうだった。
mineとサンプルの具体例を構成してみた。
sample3がなぜYesなのかを考えていると、大体の条件はfalseにして置けばOKなことに気づいたので、その方向で考えていくと解法がわかった。
計算量は適当でも間に合いそうだなーと思っていましたが、BFSで次の辺を見つけるパートを合計O(N^3)でやらないといけないことに気づき、少し考えたけど、すぐ分かって良かった。


あとで聞いた話だと、64bit高速化とかで乗り切ったチームとかもいたっぽいですね。
解法の証明は甘々にしかしてなかったので怖かったですが、１発で通ってびっくりした。

この問題不思議な問題で、なんかプロコン慣れしてる人ほど苦しんでたんじゃないかと思います。
解法自体のユニーク性、O(N^3)に落とすパート、面白い問題だと思いました。
少し感動して気持ちが上がった。

この時点では２位だっけ。

H

とりあえずIの両辺が10^9の正方形のケースでの解答の構成をチームメイトに依頼して、Hを考えた。

なかなか一筋縄ではいかないなぁと思った。
とりあえず、無限判定について考えてみると、無向辺で繋がってる頂点を縮約してやるといい感じになることに気づいた。
無向辺だけ見たときにサイクルがあればダメで木になるので、木を頂点としたDAGで最長経路を求められれば良さそうとなる。
木の最長経路パートは、

「木に分解」「DAGを作る」「DFSする」「DFS内でダブルスイープ」とやることを分かりやすいパートに分割出来て、あまり頭を使わずに実装できるので量は多めだけど楽な実装だった。
それでも量は多い実装なので、１発で通ってびっくりした。

「木を頂点としたDAGにすればいい！」って気づいたときは感動しました。

また、グラフを変換する方針があるらしいです。


面白い方針だと思ったのですが、少し実装の見通しが悪くバグのリスクが高いこともあり、僕なら木に分解する方針を選びます。
一般に「自分の書き慣れた形」を組み合わせてコードを書いていくとバグを出しにくくなる気がしています。

I

Hやってる間にmineが一辺10^9の正方形の構成を思いついてくれて、それを長方形に拡張したときに何が問題になるかとかの部分まで考えてくれていて、それを聞いたら解法を思いついた。
制約からルートで分割しそうなオーラは感じていたんですが、どういう分割をするのかは思いついてませんでしたが、チームメイトと議論してるうちに正しい解法へとたどり着けました。チーム感を感じたり、そもそも解法が面白くて感動したりで、気持ちが上がった。
extgcdあんまり使い慣れてなかったので不安でしたが、１発で通ってびっくりした。

この時点では４位と２完差の３位だったし、９完が出てもペナルティで勝てそうだったので３位を確信して少し肩の荷が降りました。

K

上にも下にも差があったので解いてもあまり変わらなさそうでしたが、１時間弱あったしやりました。
気が抜けたこともあり、睡眠不足が効いてきて意識朦朧としてました。
peryaudoと話してたら和んだ。

結局解けず終了。

      • -

とりあえず解けなかった問題に関しても感想を書きます。

J

三角形と円の共通部分面積のライブラリは持っていたのですが、探索方法が思いつきませんでした。
解説でいろいろアルゴリズムが紹介されていてすごかった。
きゅうりに教えてもらった解法を上げておきます。

x軸方向とy軸方向で独立に３分探索をします。
というのも、多角形が凸多角形なため、x軸方向だけで中心を動かすと凸関数になっています。y軸方向もしかりです。
なので、x軸で３分探索をして、その評価関数内でy軸方向の３分探索をすれば良いです。

補足：まず、例えば長方形のときとか凸関数ではない。（ただ値が変化しない区間は必ず最大値を取るということは証明できるかもしれない）
あと、面積が０になる区間はうまく避けないと三分探索が機能しないので注意しないといけない。

K

唯一不満を持った問題です。理由は思いつきようがないようなマイナーな知識を要求するだけの問題だからです。（申し訳程度の半分全列挙はありますが。）
いや「こんな知識を知ってるなんて、よく勉強してるなぁ」という風に、一応一理はあると思うんですが、デメリットの方が多いと思います。
あまりマイナーな知識を要求されると大会に対する対策のしようがなくなり、モチベーションが下がります。
また、ICPCはネット検索などもできず論文を検索したり出来るような大会ではないので、「出典：〇〇」のような問題は少し場違いに感じます。
参加者のフィードバックとして参考にしていただけると幸いに思います。

ただ、この知識自体はとても興味深いものです。
もしブログなどで出会ったとすれば素直に感動したりしそうです。
出典の本に関しても関心が高く、ぜひ読んでみたいと思います。

コンテスト後

体調最悪で、解説まではだいたい寝てました。
PFN勢がたくさん来ててすごかった。
解説は結構じっくりやってました。
順位表解凍はネイティブな感じでいい感じでした。
終了時の予想通り、前述の通り３位でした。
ただ、１位が全完していたのは予想外でした。SJTUさすがだなぁ。
３位はつくば賞とPFN賞をもらえました。

まとめ

日本のICPCは本当に上質なコンテストで、今年も本当に良い大会でした。
去年の参加記にも書いたことと少し被りますが、他のアジア地区よりも、クオリティが高いと思っています。
会場設営、スケージュール、コンテンツ、問題セット、運営・進行、スポンサー、放送、などなど、全てにおいてコンテストに関わる人の熱意がすごく感じられ、参加している私自身とても幸せな気持ちになりました。本当にありがとうございました。

他にも書きたいことはありますが、とりあえずまずは11/6あたりのジャカルタ大会頑張ります。