昨年の国内予選は敗退という結果に終わってしまいましたが、折角なのでICPCチーム(僕+Hyado+hotman)で参加する事にしました。
意気込み
去年の北大合宿・会津合宿・模擬国内・国内予選・合同チーム練と何度もコンテストで競った早稲田3チームで出る最後のコンテストになりそうだったので感慨深いものがありました(内1チームのお二方が今年でICPC引退)。順位は毎回割とバラバラだったのですがICPC国内予選本番では3チーム中最下位に沈んでしまったので何とか良い結果残せると良いな〜と思っていました。
コンテスト当日
開始が13時からで起床不安だったが、何とか3人揃ってコンテスト開始
ABは難易度順だろうという事で、A:kattu B:Hyado C:hotmanで読むことにした
Aの英語が読めずに大変辛い気持ちになる 読めたので書くAC(0:12)
Bを読んでいたhyadoに中央値管理するライブラリ持ってる？と聞かれたので、持ってないので頑張って書いてと答える しばらくすると通る(0:26)
Cでhotmanが苦しんでいたが取り敢えず問題を読むことを優先してEGI辺りの問題概要を共有した
僕E、HyadoがF、hotmanが引き続きCを考える
Eは牛ゲーの匂いを感じ取ったが実装の自信がなく、丁度Cの誤読が発覚したタイミングで、D_iが負にならないことだけ気をつけて！と遺言を残してCとEの担当をswapした
程なくしてEが通る(1:10) Fの相談をHyadoが持ちかけたところhotmanがCHTで解けると言ってサクッと実装してAC(1:26)
次通すべきなのは明らかにCだなという話になり僕Hyadoの2人で考察に回って、hotman先生がIをやることに
Cは余事象考えないと辛そう→値が全て異なる時最小値で区切れば再帰的に出来そう→最小値が複数ある場合も一番右側で区切れば良さそう？みたいな話になりHyadoが実装し始める
I、問題の認識に一部抜けがあったようだがそこを修正するとサンプルが合いそのまま通る(2:20) hotman天才すぎる
その間Gを考えていた 36/2=18いかにもな数字だな〜と半分全列挙を疑うが考察が進まず、+を適切に圧縮して位置を全探索かな？とか言っていて、hotmanにそれを話すと普通に半分全列挙で解けそうと言われる 確かにであることだなぁ
hotmanがG書くことに 何故か僕もGを書いていた 途中Cのデバックに呼ばれている間にhotmanのGが大体書き終わる
Cのバグが取れて通る(2:52) Gも1WAを経た後通る(3:05)
今日ここまで何もしてないけど順位表を見ると4位とかでテンションが上がる
後一問解きたいね、という話になりH問題を3人で考えていた
最初5手で行ける頂点が分かればいいね→実装は頑張れ！w みたいな話になってhotmanが実装し始める
やることないなと言ってKを見て手で漸化式を解いていた hotmanもHの実装を無理だと悟ってKの考察に加わった
HyadoはKを離脱してD問題を読んでいた
Kは複素数で表すとかなり綺麗な形になって、(A+Bi)進数みたいなのを考えればいいね→何もしない or 1を引いて割るという操作を繰り返せば解けそうという結論に
Dも計算量怪しいけどDPで解けたということでHyadoが熱烈実装 残り10分時点でDのサンプル2を投げられ手で解いて！と言われたので手で解いた
Kは結局永遠に割り切れる場合を見逃してTLE Dも1分前にサンプルが通ったが普通に計算量がキツかったぽくTLEでコンテスト終了
凍結前6位で最終結果9位 早稲田内1位達成！(わいわい)
模擬地区お疲れ様でした〜(hotman先生が無双して9位) pic.twitter.com/LnllRfmDL0
— かっつ (@_KKT89) 2021年3月7日
まとめ
JAGの皆さんコンテスト運営ありがとうございました。
来年こそはアジア予選に出場したい……
