アドベントカレンダー2021 9日目の記事です。

はじめに

こんにちはebiです。11/5(金)16:30~19:30で行われたICPC2021国内予選ににチームImperishableで出ました。
メンバーはImperi、ebi、0214sh7です。
ICPCアジア横浜大会への進出条件はざっくりと書くと学内3位以内かつ全体20位以上で学内4チームとしては厳しいがワンチャンあるなあって感じでした。

以下ebi視点でいろいろ書きます。

当日まで

traP主催のチーム練バチャを3回やりました。
個人ではAOJ-ICPC国内予選の問題を中心にぼちぼちやってました。

チーム的には
Imperi 構文解析/考察担当
ebi 重実装担当
0214sh7 DP/実装担当
て感じにしていました。

当日

15:00くらいに部室に行って適当な問題を解いていたらImperiが来た。
適当に1時間くらいうだうだしてS622に行った。

すくが16:15くらいに来てトイレに行ったり水を買いに行ったりしていたら16:30になった。

コンテスト開始時間になるとサイトにアクセスできません！
「まあ、いつもの」
となり1分後にぬるっと開始。

いつも通りAをebi、Bを0214sh7、C以降をImperiが読む。

ebi 「A簡単」
0214sh7 「Bちょっと時間ほしい、UnionFindかな～」
Imperi 「C構文解析っぽい」

ほどなくAをAC。

0214sh7 「サンプルあった、うわ出したくねえ～」
0214sh7 「wrong answer」

となり全員がBを読む

Imperi 「連結かつ0列目が含まれてればいいよ」

0214sh7 が実装してAC。

CはやばそうなのでDを見る。

0214sh7「3つの集合に分けてそれぞれのsumのminを最大化」
Imperi 「和ならdpで二つ求めればいいやん」
ebi 「あー、完全に理解しました書きます」

後ろで拡張Dijkstraというワードが聞こえて多分得意系だな～と思うなどしながらDを書いてAC。

Eの概要と考察を聞くと

ebi「タクシー乗る回数を頂点に含めばよくない？」
Imperi & 0214sh7「いや、それだとダメじゃない？」
ebi「できました。実装します」

というやり取りをしてEを奪って実装を始める。

最初$O((N^2+NM)\logN)$を書いて「実行終わりませんね～」と言ってると

Imperi「パソコンのスペックじゃね？」
と言いImperi PCで実行することになる。

ACL使っていたため環境の違いでぐちゃぐちゃになり15分くらい虚無の時間が発生(これマジでごめん)

実行が終わらないので高速化しないとダメだねってことになりぐっとにらむとタクシーに乗る回数は50回くらいまではまじめに拡張Dijkstraをしてあとはいい感じにDijkstraすればいいことが分かったので実装開始。

うおおおおおおおおおおおおおと言いながら書いて投げるもWA

ebi「あ、カスをしていました。殴っていいよ」

修正して投げるもWA

ナニコレ、通ってるだろ～と言いながらPCを15分くらいにらんでるとやばい個所を見つけてしまいました。

Dijkstraでタクシーの乗った回数と通った道のcostを持ってるんですが答えの計算でどっちもタクシーの乗った回数として計算していたので直して出すとACしほっとする。

僕がぐちゃぐちゃになってる裏ではCの考察ができたらしくImperi、0214sh7が並列実装している。
残り15分でやることもないので順位表を見ながら二人を応援していると残り15秒くらいで

Imperi「サンプルあった」

と言うもコンテストが終了。

AB-DEの4完で29位でした。KyopRo-jinに負けたので学内4位で敗退です。

Cあと数分だったのでかなり惜しかったな～など懺悔会と反省会をした。

帰る途中にtqkとjss_techにあった。

そして肉を食べました。「最高！」

感想

大きな破滅はなかったが小さいカスが積み重なってたのはよくなかった。
各々の担当とまったく違う感じになってしまい笑った。
チーム的には国内予選敗退だったがパフォーマンスは出せたかなって感じ。
来年は黄色になって出たいね！

アジアに進む方々は頑張ってください、応援してます！！！！

明日はHmcmchさんです。お楽しみに！