AMATSUKAZEというチームで参加しました。

国内予選

10位でした。

ICPC 2023/2024 国内予選参加記（ebi 視点）

はじめにICPC 2023/2024 国内予選はnoya2 [https://atcoder.jp/users/noya2]、shobon[https://atcoder.jp/users/shobonvip]、ebi_fly [https://atcoder.jp/users/ebi_fly]の3人でAMATSUKAZEというチームで参加しました。 模擬国内の参加記はこちら [https://trap.jp/post/1914/] 当日まで毎週火曜と金曜日に国内予選と模擬国内のセットを走っていました。バチャのナンバリングが21なので、21回セットを走ったらしいです（頑張った）。…

東京工業大学デジタル創作同好会traPebi

メンバー

• ebi_fly

筆者。M1でラストイヤー。構文解析と木が得意。

• shobonvip

B3。フロー担当大臣。寿司打3万5千

• noya2

B2。構築、幾何が強い。

事前準備

• Universal Cup というもので毎週5hを走っていました。
• 横浜の過去のセットをバチャ（2016 ~ 2022）
• 5月くらいの早い段階でUSキーボードを使うようにしました。アジア大会は基本USキーボードなので早いうちに慣れるとよいと思います。
• ライブラリを準備

day 1

13:00 ~ 14:00に受付をしないといけないので、12時くらいにチームメイトと集まり、お昼ご飯を食べた後会場に行きました。

東工大の面々や夏合宿であった人がいたので、ちょっとお話をしたら開会式が始まりました。

開会式後はリハーサルがありました。リハーサルでは本番と同じ環境でコーディング & 提出ができるのでいろいろ試しました。TLEを出すときに、TLEを意図したコードがコンパイラの最適化によってTLEではなかったりでちょっと手間取りました。typoチェッカーが煩わしかったので、リハーサルが終わったら消し方を調べたりしました。

リハーサルが終わったら、チーム紹介がありました。我々は書くことが無かったので、競技プログラミングの問題を書きました。楽しんでいただけると幸いです。ツイートにある3枚目のスライドが面白くて好きです。

チーム紹介が終わったら解散になったので、外に出るとtonosamaの人たちと会い一緒に中華街でご飯を食べることになりました。台湾料理の店に入り、ルーローハンを食べました。おいしかったです。

家に帰り、ABCにでて、23時にはベッドに入りました。

day 2

6:30くらいに目が覚めました。8:40 ~ 9:10に受付をしないと失格になってしまうので、早めに移動しました。会場には8:30分くらいに着き、東工大チームであるacidrainがいたので、軽く話していたら受付がスタートしました。

会場に入り、ライブラリの紙や水などを机に出し、コンテスト準備をしました。知り合いと軽く話をし、トイレに行くと始まりのあいさつがありました。その後コンテストが始まりました。

コンテスト

初動は、環境構築 + テンプレート打ち（ebi）、A (shobon) 、B (noya2)でした。

パソコンのログイン、DOMJudgeへのアクセス、CLionのライセンス登録、CLionのtypoチェッカー外しを行い、テンプレートを打ちました。それ以外の設定はしていません（CLionはデフォルトで補完が効くので楽で良いです）。

テンプレートを打ち終わると、shobonくんがAができたというので書いてもらいました。ほどなくして、通りました。(0:09)

その後、noya2くんがBできたというので書いてもらいました。

僕は、D問題を読みました。問題文を見て、構文解析だ！と一瞬なりましたが、全然違うことに気づき、ちょっとしょんぼりしました。読み終わった後、distinctな連続部分文字列は独立に最短にすればよいことはわかったので、区間で分割するのがいいなとなりました。すると、区間DPでできることがわかりました。具体的には

$$DP[l][r]:=区間[l,r)を圧縮したときの最短文字数$$

とすると、 $[l,r)$ は真ん中で分けて $DP[l][m]+DP[m][r]$ とするか、 $r-l$ の約数で $[l,r)$ を分割し $D(S)$ という形にするものの最小に更新していくとできます。
始め、 $D$ が $1$ 桁でない場合もokだと勘違いして計算量が心配になりましたが $1$ 桁であることが分かったので大丈夫でした。計算量は $O(D|S{|}^3)$ です。復元が要求されるので、DPがchminされたときのものをメモしました。

D問題の解法が分かった段階で、Bが大変そうでPCを変わってもらったので書き始めました。再帰の大枠を書いた段階で、Bができたそうなので交代しました。ほどなくしてFが解けたとshobonくんが言ったので「どれくらいで実装できますか」と聞くと5分くらいでできますと言ったので先に書いてもらうことにしました。

Bが通ると、Fを書いてもらいました。(0:48)

次にKを読みました。問題文読解力なく、よくわからなかったんですがFがバグったので印刷してPCを変わると言われたので、Dを書きました。Fのバグがわかったそうなので直してもらうと通りました。(1:06)

Dの繰り返しの文字列長をミスっていたことがわかったので丁寧に直すと、サンプルが合いました。自信たっぷりだったので、提出するとACでした。(1:18)

Eの考察ができたらしいので書いてもらいました。僕は引き続きKを読み、概要をnoya2くんに伝えると、僕が苦手問っぽいのでお任せしました。順位表を見ると、Jが通されていたのでJを読みました。なんじゃこりゃとなりいったん放置してHを読みました。順番が任意なのがやばくて、dpじゃ無理だろとなりました。1人だったらソートして貪欲でいいというのをshobonくんに言われ、確かにとなりました。

Kができたらしいので、解法を聞くと良さそうだったので実装をお願いしました。

shobonくんがEをバグらしているらしいのでコードを読むと、高速ゼータ変換の箇所は大丈夫だったんですが、他で明らかにやばい個所を見つけたのでgot事なきを得ました。(1:52)

ここらへんで順位表を見ると、我々が出遅れていることがわかりました。GとKがかなり通されていたので、Gをやることにしました。

noya2くんにKを実装してもらいほどなくして通りました。(2:16)

Gは苦手っぽいので（なんか苦手ってめっちゃ言ってない？）二人にお任せし、僕は得意な木の問題であるJを見ました。木の問題は、まず線グラフ（数列）の場合を考えるといいんですね～と言い考えましたが全く見えませんでした。木DPを考えると、2乗の木DPになりお手上げやとなっていると、clarでac_priorityqueue.cppが手違いでババーンとなっているという旨が書いてありました。priority_queue使うことが周知されたようなものなので、やべ～～と言いながらヒントをもらったようなものなので考察することにしました。全く手掛かりがなく、お手上げ状態になりました。

Gができたようなので、書いてもらいました。実装が終わりだすと、TLEとなり困りました。timeコマンドで時間を測ると5secくらいであちゃ～となり、std::mapをstd::unordered_mapにして時間を測ると3secくらいになったので投げると通りました。(2:47)

Hの見た目がやばすぎて、dpも絶望的なのでshobonくんにフローっぽいですというと、笑顔で「これはフローっぽいですね」と言われたので笑顔になりました。いろいろ頑張ってもらうと燃やす埋めるになり最小カットになるようなのでdinicを書いてもらいました。

Jで、noya2くんに、はじめ priority_queue に $f_i$ を入れ、 $f_i$ がpopされたら $f_i\times 3$ を入れるということをすると、貪欲になりますと言われ、天才だとなりました。チームメイトが天才だと最高だぜ！となるとなんかそれっぽい解法が生えたので実装してもらいました。Hがバグりまくりらしいので、デバッグを手伝うと、燃やす埋めるの辺の貼り方が間違えていたらしいので直してもらいました。

noya2くんの実装が終わりサンプルを試すとバグってるらしいので、貪欲が嘘の可能性を考えサンプルを手でやってみました。あってますが、聞いた解法だと破綻する場合を見つけたので伝えると考慮していないことが判明し直してもらいました。

Hがバグりまくりなので、印刷してデバッグをしました。Jができたらしいので提出すると、TLEが返ってきました。苦しい気持ちになりいろいろデバッグすると、仕事を割り当てた頂点 $v$ と根のパス上で、もう仕事が置けないことがわかる頂点は $v$ から単調に並んでいると思っていましたが違うこともあることが判明しました。noya2くんに、パスのargminとパス加算ができればその判定ができますと伝えると書いてくださいと言われたのでライブラリからHLDを取り出しtypingしました。

HLDのtypingが終わった時点で残り $30$ 分で、焦りと $30$ あれば実装できるなという自信とで感情がぐちゃぐちゃになってました。typingが爆速なshobonくん（寿司打3万5千）に遅延セグ木を打ってもらっている間にHLDの確認をnoya2くんに任せ、僕は方針をバチバチに固めました。

遅延セグ木の打ち込みが終わり印刷してもらい僕はゴリゴリ実装していきました。必要なのはargminとパス加算だけなので、丁寧に実装すると、サンプルが合い、ニコニコになりました。ランダムケースで試すと、遅延セグ木のassertで落ちまくり顔面蒼白になりました。デバッグしていると、無限再帰を踏んでしまい、PCが落ちました。絶望的な顔をしていると、昨日tonosamaの人たちにメモリを確保しまくるとPCが落ちてすぐ起動しましたと聞いていたのを思い出し落ち着きました。復旧したら、noya2くんからHLDで親を配列に入れ忘れていることを指摘してもらい、直すと、元々のWAコードとランダムケースで異なる結果を出し、TLEも大丈夫そうであることも確認できたので出しました。Pendingの状態で一生そのままだったので、苦しい気持ちになり、定数倍高速化したコードをもう一度投げました。PCが落ちたときに変なことが起きたのではなど嫌な想像が脳を駆け巡りましたが、ほどなくして $1$ つ目の結果がACであることが返ってきました。(4:55)

そして、Hの辺の貼り方をいろいろ変えてもらいだしましたがダメでう～んとなっているとコンテストが終わりました。 $1$ チームだけトラブルで数分の延長があったので待っているとそれも終わり正式にコンテストが終わりました。

コンテスト後

Speed Starが速すぎてやべ～となったり、SPJも速くてすげ～～～となったり、Bocchi The Techが凍結後にたくさん出していてやばいとなっていました。

台湾の国立陽明交通大学のNYCU_FriedShrimpというチームが我々の机に来て、team introductionに書いた問題を解いたのでジャッジしてほしいと言われたので、聞くと、よさそうだったのでいいね！的なことを言いました。台湾のお土産のケーキがあるからみんなで食べてくれと言われてお菓子をもらいました。社交性がすごすぎるぜ！

ジャッジの公表の時間になったので聞いてると、Iが天才でひっくり返りました。Hが最小カットで何が間違っているんだろうとなりました。

Yes/Noでkotamanegi_marunageがめちゃくちゃACしていて盛り上がったりして楽しかったです。

AMATSUKAZEは凍結後Jが通り8完13位でした。自分はあまり貢献できなかったので申し訳ない気持ちがありますが、夢にまでみたICPC Asia Regionalの舞台で戦えて良かったです。チームメイトには感謝しかないです。

懇親会

机を片付けて、すぐにパーティー会場に行けと言われたので行きました。たくさんの食べ物が置いてあったのでニコニコしながら唐揚げをたくさん取り食べました。おいしかったです。

色々な人と話ができてよかったです。企業ブースも少し行き、たくさんのものをもらいました。ジャッジの方とも話ができて楽しかったです。こういう懇親会はいいですね。

ポエム

大学1年生から競技プログラミングを始め、2年生で国内予選に初参加したのですが、全く歯が立たなかったことがついこの前のような気がします。憧れていた舞台で競技ができてチームメイトには感謝してもしきれないです。ありがとうございます。来年以降も頑張ってほしいです。応援しています。

競技自体には後悔や反省もありましたが、やれることはやったと思います。

M1で早生まれではないので、私はこれでICPC引退です。競技プログラミングは続けようと思うので、これからもオンサイトで会ったときはよろしくお願いします。JAGには暇ができたら入ろうと思います。

ICPC運営の方々、JAGの方々、ジャッジの方々、スポンサーの方々、アルバイトの方々、そして一緒に競技をした方々、本当にありがとうございました。最高の大会でした。

p.s. 研究 & 就活やばすぎ！HELP！