ICPC2017国内予選参加記

Pocket

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

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

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

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

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

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

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

当日まで

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

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

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

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

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

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

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

その他に、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したら解けました」と答えたところ、

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

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

きひろちゃんさんの解法を聞くと、問題文に記述されている状況を素直に利用した、頭のいい解法だと思いました。

私は「ビット操作で解けるはず!」という固定観念の下で、ビット操作で解く方法を無理やり編み出してしまったようです。固定観念は良くないですね。

イミフな解法はまた別記事にします。書きましたICPC2017国内予選 F「リボンたたみ」黒魔術解法

感想と反省

今回、初めてICPCに参加して、良い結果を残せて、とても楽しかったです。

予選通過は狙える範囲だと思っていましたが、まさか10位になれるとは、望外の僥倖ですね(適当)。

今回良かったのは、苦手なEを捨ててFに集中したことと、それを可能にしてくれたチームメンバーの活躍ですね(B,D,Eがどれも苦手なタイプだった)。

今回反省すべきなのは、Fで固定観念から、証明のしかたすら分からない黒魔術を生み出したことですね。

結果として解けたから良かったものの、もっと汎用性の高い考察能力を身に着ける必要がありそうです。

ともあれ、無事に国内予選を通過できてよかったです。この夏は競プロ三昧にしたいですね(あとコミケ行きたい)。

Fの解法を別記事で書くので(書きましたICPC2017国内予選 F「リボンたたみ」黒魔術解法)、しばしお待ちください。では。

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする

コメント

  1. […] ICPC国内予選参加記で書いた通り、F問題の自分の解法を書きます。 […]