ICPC 2018 国内予選 参加記

ACM-ICPC 2018 国内予選 に参加したので参加記書き書きします。

去年の参加記は ↓ これ

ICPC国内予選2017参加記 - shining segtree

去年のチームメンバー 2 人が大学を去ってしまったので、別の後輩2人 ( AtCoder ID :  f_t_ikt, mint )を連れて参加。

二人とも競プロ歴は1年以上あり、練習だと C までは解けていたので、僕が D を通せるかどうかにかかっていた。

結果は 4 完 35 位、大学内で1位なので予選通過です。やったね。

ICPC に B1 から参加し続けて、B4 でやっと国内を突破できました。長かった。

チーム名は FunamiYui です。愛をこめて。

コンテスト前

競技用 PC がやたら不安定だったり宗教的に偏っていたりしてぶちぶち文句を言う。

突如キーボードの配列が英字になったり SKK のせいで shift + space を押すと全角入力になったり、、、

チーム練習が明らかに足りてないため、コンテスト前に戦法を固める。

どうせ D まで解けなければ国内突破は無いため、僕が開始から最後まで D 問題に取り組み、後輩たちに A ~ C を任せることに。

コンテスト開始

f_t_ikt が A を開く。同時にブラウザ2つ並べて D も写してもらう。

D の問題概要が把握できたので PC から離れる。

D を解いてる最中のことは知らないので、後から聞いた話を書いていく。

A は割と自明だったようで、 f_t_ikt がすぐ AC。

コンテスト全体で 1 番最初に AC を取ると Fixstars さんから賞がもらえるので息巻いていたが、学内のほかのチームに負けてしまった様子。そのチームは全体 3 位だった。強すぎかな？

そのあと B を mint が読み、実装を始める。

並列で f_t_ikt は C を読み考察。

B の実装が終わるもバグる。D を解きながら不穏な空気を感じるも、 D が結構見えていたのでとりあえず 2 人を信じて放置。

このあたりで D の考察が終わる。

計算量をちゃんと計算する、ということ自体が問題の核になっている問題に去年殺されてしまったので、ちゃんと計算した。

AtCoder 系問題のおかげで、全チームプレーオフ状態になるには勝敗が同じ値になるとかにはすぐ気づいた。

図を描くと総当り表なので試合結果は半分、最悪でも 8 試合中 4 試合勝つ場合の数 * 7試合中 4 試合勝つ ... みたいな感じなので、高校数学をし全探索できることを確認。

試合の進行度と各チームの勝ち数、負け数をもって dfs すれば大丈夫そう。

実装はすぐだったので紙で書ききった。

写すだけになった時点で B のバグ取りが進む。まだダメな様子。

PC 借りて D 写して提出。 AC。AD 2 完。

B の様子を聞くと、 f_t_ikt がデバッグにちょっと顔出してて、C がまったく分からないとのことだったので、とりあえず C を受け取ることに。

f_t_ikt と mint は模擬でも 2 人でバグとって AC 掴んでいたので、二人に任せる。

このあたりで順位表を見て、B で他のチームも苦戦していることを伝える。ゆっくりやってくれて大丈夫、みたいなことも言ったつもり。

C はぐっと睨むとなんか解法が生える。

累積和でホイ、得意すぎる。すぐ紙に書く。

書きあがると B のバグ取りが進んでいた様子。まだ合わない。辛そうにしている。

ちょっとだけ PC を借りて C を写し走らせる。合わない。印刷して PC を返す。

C のバグを発見する。ごくしょうもないもの。

PC を借りて直して提出。AC。ACD の 3 完。

この辺で泣きそうになる。

直後に B のバグ取りが終わる。 mint が辛そうにしている。どんなバグだったんだ。

AC。ABCD 4完。順位表を見ると通過できそうだったので安心する。

その後はなにも集中できず終了。

順位表ばっかり見てたら監督の先生に「あのチームは問題解かないのかな？」とか言われていたらしい。

まとめ

地区大会に参加する方々はよろしくお願いします。

競プロはじめたのが B1 の ICPC だったので、ICPC が終わると僕の競プロ歴が 1 年区切りを迎えることになっています。

競プロ 4 年目も、精進していこうな。