ICPC2021国内予選参加記

あ

国内予選に参加しました
チームメンバーは去年と同じくM1数学科の se1ka2 drogskol shakayami、チーム名は MATHKU です
1年前から色を上げたチームメイト2人とレートを100下げた僕、いったいどうして

数ヶ月前の情報では京大最強の Heno World が出れないとか、出場するレッドコーダーが数人しかいないという話だった気がするんですが、全てガセでした
京大は去年上位勢がかなり引退したんですが、暖色が5人くらい入学して来たので中々険しい
Heno World と KUB1 がかなり強いので、大学内3位を目指すなら他には勝たなきゃなみたいな感じ
模擬では実現できていたので可能性は無くも無いかなと思っていました

コンテスト

時系列周りがかなり怪しい

A,B をチームメイトに任せて C を読む
操作のイメージが完全にはつかず、自由度がかなり高そうかなといった印象
全然分からんし俺の担当じゃ無い気がしたので一旦 D を読む

この辺のどこかで A,B が通ったはず
2完時点では10位以内に入っていたはずで、出だしとしてはそこそこ
C が全然通されてないことも多分同じ時に気づく

D は最初毎回3本のポールを自由に選択できる問題と等価だと思って ABC143-F の解説を読んだりするも、チームメイトに嘘を指摘される
Dも分からないので、CD を頭の片隅に置きながら E に逃げる

E は(頂点,乗車回数) を新しい頂点とするグラフでダイクストラをやればいいですねという気持ち
乗車回数が 10000 とかになると無理だけど、乗車回数が50回以上なら最低乗車回数にするのが最適という話を se1ka2 と話して思いつく
実装をあまりしたい気分じゃなかったので se1ka2 に押し付けて F を読む

F は完全マッチングを１つ固定すると、全ての非マッチ辺が交互サイクルに入ればいいということまではすぐ分かる
言い換えとしては筋が良さそうだけどそこから先はぱっと分からず
交互サイクルとかの話は se1ka2 の方が得意そうなのでどうしようかなという気持ち
上位勢が全員 A~E の5完で並んでいるので CD を解くべきとなり CD に戻る

C は負として関与する個数が高々１個に出来るんじゃ無いかと思ったけどチームメイトに反証される

D は全然分からなくて、shakayami の実験コードのおかげでこちらの予想が次々反証される
しばらく無の時間が続くも、shakayami が急に3分割と呟く
3分割が正しそうなことがすぐに証明出来て、実験コードも反例を見つけないので shakayami に出してもらい AC

E の実装が終わるも WA が出て、デバッグを手伝う
ついでに F の概要を se1ka2 に一応伝えるとDM分解という言葉が出たが知らないので無視
とにかく E のバグを取るのが先決と思い 3,4 個ミスを指摘するも通らず
結局何が間違っていたのかまだ分かってない*1

ん

結果は ABD の3完で京大内最下位
C は操作の自由度を完全に把握するべきだったかなぁ
E の実装を俺がやるべきだったかなと思いつつ、dijkstra のライブラリとか持っていないので微妙
F で向き付けくらいは思いつくべきだった

全然精進をしていないのにこんなことを言うのもどうかなとは思うが、かなり不完全燃焼な感じで引退することになり悲しい
一回くらいは予選突破してみたかったね
shakayami は早生まれで来年も出れるっぽいので頑張って欲しい

予選通過チームはおめでとうございます
今年はオンサイト出来るといいね

*1:追記:わかった