読者です 読者をやめる 読者になる 読者になる

ICPC2016 国内予選 参加記

競プロ ICPC

おそらく最後のICPCの国内予選です。
7完2位でした。
大きな戦略ミスと大きなハマりがなかったので良かった。
メンバーは去年と同じ(peryaudo,mine_studio)
今年はJOI本戦勢・JOI春合宿勢・CTF勢の1年生チーム(peryaudoを名乗っているチーム)がいて、来年以降にも期待が高まっています。

印刷を失敗したせいもあって序盤の立ち回りが崩れたのであまり参考にならないかもしれませんが、コンテスト中の流れです。印刷順序にはお気をつけください。

〜開始

・peryaudoがPCを買い換えてプロからエアーになってた。僕もmacbook趣味 の方なので使いやすかった

開始〜

・問題を自前プリンタで印刷しつつ、mineにエイリアスとかの環境を整えてもらう。
・後ろのページから印刷されてしまい、序盤の問題を読めなかったのは結構失敗だった。
・序盤のペナルティが増えるが、コンテスト全体の戦略を詰める時間が増えたので、デメリットだけでもなかったかもしれない。

A

・始まってすぐperyaudoに投げた。概要知らない。7分くらいで通してた。
・印刷を失敗して、仕方ないから後ろから順番に問題を読んでいた。
・H読んでシンプルなグラフ問題だし、そのうち解こうと思った。
・Gは幾何だったので、とりあえずmineに問題読解を投げた。
・F,Eあたりもざっと目を通した。

B

・Aが通った頃にはまだB問題の印刷が終わっていなかったため、とりあえずこれもperyaudoに投げた。
・その間にDを読むと区間DPだったので、自分で実装することにした。(DPは自分でやった方が数段速くなるという経験則)
・Cはperyaudoに投げようかなと思った。
・E,F,Hあたりの解法もこの辺で考えてわりとすぐ思いついてた気がする。
・peryaudoはサンプルが合わなくてちょっとハマったっぽい。
・問題文読んだりしたそうだったから交代した。

D

・書いた。
区間DPをデバッグしてしまった。
・直った、通った

B

・D書いてる間に無事原因がわかったらしくすぐAC

C

・Eを読んで、立方体の交差によって減る表面積を計算する関数が要りそうだったので、その部分をperyaudoに詰めてもらうことにした
・結局Cは自分でやることにした。
・問題概要とかを伝えるほどでもないくらい実装軽かった。
・C問題:上限について思いを馳せるとエラトステネスっぽい操作だから素数っぽい感じになることがわかった。面白い。答えが最大になるケースがサンプルに入っていて優しさを感じた。

H

・バグる要素がないし、ライブラリさえ写せば残りのよりもすぐ書けそうだったのでやった
・ライブラリ写経は他の人に任せてもいいのだけど、EもFもすぐ書き始められる程度に解法スタックが溜まっていたので自分で写した。(独自のマクロとかもあるし、書いた本人である自分で写す方が多分早い)
・最小を最大化だと思ってて誤読で危なかったが、正しいバージョンもすぐわかったので良かった。
・H問題:S,頂点のノード(n個),辺のノード,Tからなるグラフにフローを流す。S→(頂)に流量x_i(後述)、(頂)→(辺)に流量1の辺(2m本)、(辺)→Tに流量1の辺を貼る。最小の値Lを0~nまで試す。x_iをLに設定して流してmaxflowがnLでなければNG。OKなら最大の値RをLから1ずつ増やしながら試す。このとき、グラフは初期化せずに対応する辺の残容量だけを増やす。容量を増やした後に流し直して、合計のmaxflowがmなら実行可能。流し直したときに最小流量条件を満たさなくなるかもしれないと思うかもしれないが、S→(頂)の辺を逆流させるような増加流は明らかに最短路ではないためここに逆流は起きない。
デバッグも特になくAC

E

・立方体の交差によって減る表面積を求める関数と、それが1以上の組に辺を貼ったグラフまでperyaudoに実装してもらった。
・この間にGの概要を聞いて、解法を考えたけどすぐにはわからなかった。x,yを独立にするところまでは考察が進んだ。(解説では「重心」の一言で解決してる部分)
・残りのパートは悩ましい要素のある実装なので自分でやった。
・この辺りで2人の仕事はほぼなくなったので後ろで見てバグがないかチェックしてもらってたけど、結論から言うとバグった。
・正直redcoder(しかも変数名わりと適当)が何を書いてるのかを同時に追うのは相当難しいし、チェックすべきポイントみたいなのをまとめておくべきなんだろうな。(改善の余地あり)
・最初に訪れたフラグをtrueにし忘れるというアホバグ埋め込んだ(しかもこの辺の出力見て挙動チェックしたはずなのに・・・)
・1WA食らってしばらくデバッグ(ダメ)
・AC

F

・解いてる間にGのサンプルを図示してもらう。
・特に何も起きなかったので解法だけ書く。
・周りに白マスをつけて1周り拡張する。
・包含関係は根付き木になるため、それをまずは構成する。
・各マスの「そのマスが属するグループ番号」と「親グループの番号」を求めていくことにする。
・左上のマスから順に、まだグループ割り当てがされていなければDFSを開始する。
・同じ色の連結成分全てに現在のグループ番号を割り当て、隣接している異なる色のマスについて、そのマスがまだグループ割り当てされていなければ親グループを現在のグループに設定する。
・求めた情報から根付き木を復元するのは難しくない。
・根付き木はカッコ列に変換する。子のカッコ列は辞書順にソートして並べる。これで正規化が出来て比較が容易になる。(ちなみにこの部分は、前にperyaudoのコーディング面接練習に付き合ったときに出題したらちゃんと解かれた)
・2個ずつ処理するのが面倒だったので、2*テストケース数分だけ文字列が入ったvectorを作って、最後に全部出力した。

G

・2乗和なのを失念していて、候補の座標はいずれかの頂点と同じx座標,y座標のn^2通りでいいと思って書いてしまい、サンプルが合わなかった。
候補が2^40通りより減らせなくて結構悩んだ。
・N=20が2^20を連想して少し惑わされたが、それを利用できそうな道は思いつかなかった。
・問題を整理して円を書いてみたら、集合の候補がだいぶ減りそうな方針を思いついた。(具体的にどれくらいかはわかってなかったけど言われてみると確かにM^2程度だ)
・円の交点となるような座標について、そこを含む円の集合を計算して、それらのコストを最小化する座標を求めてそれを候補とすれば良い。
・(+もとの頂点の座標も候補に入れる)
・正しい解法を思いついた時点で残り18分で、peryaudoに幾何ライブラリを写してもらって、mineに方程式を解いてもらって、僕はその他の実装を詰めた。
・なんとか実装は終わって嬉しかったけど、デバッグは間に合わなかった。

以上

うーん、よく考えるとまだまだチーム戦略見直すべき点がいくつかあったけど、年々チームの立ち回りがよくなってきていて楽しい。
peryaudoにどれくらいのことを任せられるのかが分かってきたというのも大きそう。
googleのコーディング面接対策をしてからperyaudoの実装力が上がったような感触を受ける。

最近競プロで大スランプを感じていたので不安だったけれど、悪いコンディションとかがたまたま重なってただけかなぁ・・・
今回の目標は遠征費獲得(例年通りなら大学別2位)だったので大満足な結果です。