ICPC2017国内予選参加記

Pocket

こんにちは。お久しぶりです。

昨日、ICPCという大学対抗のプログラミングコンテストの国内予選があり、弊チームnasubidenamida（大阪大学）は6完10位で予選通過が確定しました。

チームメンバーは私とsnteaさん（@hogex4）とMさん（ツイッター垢しらない・名前出していいか分からない）です。どちらも今回のICPCチーム決めで初対面でした。

11位で企業賞があったのでちょっと悔しいですが、11位のチームは魔窟（東京大学）チームゆえに予選通過できないみたいなので、企業賞があって良かったように思います。

私はCとFの考察・実装を担当しました。~~Fの解法は別記事で書きます。~~書きました→ICPC2017国内予選 F「リボンたたみ」黒魔術解法

今回がICPC初参加だったのですが、無事予選通過できてよかったです。あと模擬国内予選で負けた先輩チーム（kiwidenamida）にリベンジできて良かったです。

せっかくなので参加記のようなものを書こうと思います。

1 当日まで
2 国内予選当日
3 感想と反省

当日まで

7月下旬に大阪大学でICPCに参加したい人で集まってチーム分け。

私はずっと一人で競プロをやってきたので、初対面の方も多かったです。

6人いて、どうチーム分けしようかと相談した結果、集まりやすそうな「豊中キャンパス組」と「吹田キャンパス組」で綺麗に分かれることに。

学年的に、吹田チームが先輩チーム、私が所属する豊中チームが後輩チームという感じになりました。

模擬国内では4完で22位（参加資格のあるチームでは15位）でした。私はCの考察・実装とDの一部考察・実装をしました。

模擬国内でsnteaさんが充実したライブラリを持ってきていたので、自分のライブラリの貧弱さに焦りを覚えました。

模擬国内以降は、ライブラリを充実させるべく、「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の電子版を購入し、幾何ライブラリを作成しました（紙の本はsnteaさんが持っていたので、安い電子版にしました）。

<br />

その他に、AOJのフロー関係の問題とセグ木関係の問題を解きました。最小費用流を初めて書いた。

そんな感じで、チーム練習などもせずに本番です。

国内予選当日

コンテスト開始前

先日のAtCoderのAGC017で、開始前に花澤香菜さんの声を繰り返し聞いていたら4完でパフォーマンス2900超えを達成したので、花澤香菜さんの声を聞きながら吹田キャンパスへ向かいました。

特に問題なく全員集まり、誰もライブラリ化していなかった2円の共通接線を求めるコードをその場で印刷して待機。

初手は、模擬国内と同じく、snteaさんがA、MさんがB、私がCを解く、ということにしました。

コンテスト開始直後

予定通り、snteaさんに問題ページを印刷してもらい、snteaさんがAの実装を開始。

私はCを読み始め、「周囲の最小値？面積ではなく体積の最大化？むずくね？」と思いながら制約を見るとH,W<10だったのでO((HW)^3)で間に合うということで、全探索だなーと思いました。

計算用紙には「C：全探」のメモが残っているのみです。

続いてD問題を確認し、XORが0になるように選べばいいのだと分かったので、その旨を問題用紙に書き記しました。

snteaさんがAを通したときに、MさんにBの様子を聞くと、もう少し時間が掛かるとのことだったので、snteaさんにDのXORの話をちょこっとしてからCを実装。ちょこちょこバグらせましたが、特に問題なくAC。

B問題担当のMさんとバトンタッチ。snteaに「Dがたぶん解けた」と言われ、解法を聞く（nが20以下か否かで半分全列挙とDPの場合分け）。問題なさそうだと返事をし、EとFの問題文をチェック。

Eに関して、過去に似たような問題を解いたことがあるという話をしました。そのときは完全には思い出せませんでしたが、こどふぇす2015本戦Eの「ショートコーディング」でした。→解説記事

この「ショートコーディング」の自分の解法は、まず与えられた式がどのような値を返すかをチェックして、元の形を完全に忘れて、同じ値を返す式を0から作る、というものでした。

今回は二値変数が4つあるので、16通りの入出力があるわけですね、みたいな。でも「苦手なタイプだなー」と思っていた。

そんな話をして、とりあえず難しそうなのでsnteaさんに任せて、私はFの問題文に移りました。

F問題を見てしばらく考えて、「自分が力を発揮できるタイプの問題っぽい！」と思いました。そこでEは完全に放棄してFに集中しようと思いました。この選択が本当に良かったみたいです。

Mさんがバグと闘いながらもBをACさせてくれて、snteaさんがDの実装に入りました。

このあたり、私は完全にFに集中していたので、MさんやDを解き終えたsnteaさんが何をしていたのがあまり知りません……（ちゃんとチーム戦をしようね）

Fの解法が分かった！と思いきや違った……と思いきや分かった！というようなことをしており、Dを通したsnteaさんに「こうすれば解けるはず」という説明をするも、説明中に反例が出てしまう。

なぜだと思って色々見直していると、最初に作ったLR遷移の木が間違いであることに気づき、自分の解法が正しいっぽいと思いました。

snteaさんがE解けそうとのことで実装を開始。私は「あのE解けるとかスゲー」と思いながらFの考察をゴリゴリ。

詰まったのでMさんに手伝ってもらおうと思い、「こんな数列の第i要素が桁数オーダーぐらいで分かれば解ける、というところまできました。

ビット列とにらめっこしてたら分かりそうですが難しいです」という話をしました。

ビット列とにらめっこしていると、ついに最後のピースを埋める方法が思いつきそうになりました。

PCはsnteaさんがEの実装で使っているので、Mさんに説明しながら、アイデアを貰い、最後の一歩を詰めました。（証明はしていません）

ちょうどその頃にsnteaさんがEを通してくれたので、そのままFの実装に移りました。

ビット操作やちょっとしたミスでバグを生み、時間がどんどん消費されていき、割と焦りました。

コードをちょこちょこ変更してはサンプルを入力し、ついにサンプルが全て一致するコードに到達したので、「サンプル通ったので投げます」と言ってsnteaさんに頼んでファイルDL、コード実行、提出を行いました。ドキドキです。

1回目でACし、私とsnteaさんのテンションが上がりました。

2回目でACし、コングラッチュレーション。メンバーでハイタッチしました。

この時点で6完9位でした。さすがに通過は確定ですね。

興奮冷めやらぬまま、30分ほど残っていたので、Gの問題概要を聞きました。「右手法でいけるんじゃないか？」と提案し、反例を考えていたところ、Mさんが袋小路に入る例を提案してくれました。

Mさん曰く、袋小路に入ってループしたら、そのループを無かったことにすればいいのでは、という話でしたが、ループ中に宝箱をゲットしたらアウトなので、そのチェックをする方法を考案しました。

ダメ元でGの実装に取り掛かりました。が、さすがに間に合いません。

残り5分を切ったところで、先輩チームがザワつきはじめました。

何か通すのかな？と思いましたが、とりあえずGの実装を進めていたら、先輩チームから「阪大2チーム通過確定！」の声が。

「おおっ」と思って順位表を見ると先輩チームも6完。Fを解いた段階で「先輩チームにAC数で勝った」と思っていたのですが、まさか並ばれるとは。

うっかり先輩と話しそうになるも、まだコンテスト中だからまずいと窘められました。まあそりゃそうですよね。

気を取り直してGの実装の続きに取り掛かるも、ちょうどコンテスト終了の時刻に。

弊チームは6完10位、先輩チームは6完14位だったので、2チーム通過が決まりました。

大阪大学からは2チームのみの参戦だったので、通過率100%です。しかも6完率100%です。

こうして、私の初参加のICPCはもうちょっと続くことになりました。

コンテスト終了後

終わってからsnteaさんにFの解法を説明するも、多量の考察を要する解法だったので、結論あたりだけ話しても「なんだかよくわかりません」という反応。

部屋の片づけをし、先輩チームでFを通したきひろちゃんさん（@aki33524）に「Fどうやって解いた？」と聞かれたので「なんかぐちゃぐちゃやってXORしたら解けました」と答えたところ、

後輩チームのF解法イミフ過ぎてワロタ

— きひろちゃん (@aki33524) 2017年7月14日

と言われてしまいました。

さすがに「ぐちゃぐちゃXOR」だけではなく、実際には以下のような説明をしました。

Fをもうちょい正確に言うと、最初はiXORjでLR列が出るのではと思ったけどダメで、実は、謎の関数f()にiを通したものとjのXOR、つまりf(i)^jがLR列（の前後反転？）になる、ということが分かり、頑張ってfの正体を突き止めてO(n)で再現した（iとjは最初にデクリメント）

— ふるやん (@furuya1223) 2017年7月14日