ICPC 2023/24 Asia Yokohama Regional Contest 参加記（shobon 視点）

はじめに

AMATSUKAZE というチームで ICPC横浜2023 に参加しました。
国内予選は 10 位で、横浜 regional は 13 位（東工大内 3 位）でした。

この記事を見ている人はこんな記事も見ています

メンバー

ebi_fly

構文解析、木、重実装が得意

shobonvip

フロー、タイピング、誤読、ぬいぐるみなでなでが得意

noya2

幾何、天才、数学（とくに数論）が得意

day 1

一週間前まで ICPC regional は一日イベントだと思っていました。よく見たら毎年二日にわたって開催されていました。

大岡山から横浜は2～3時間かかると思って宿泊も選択肢に入れていたのですが、前日に調べたら30分しか掛からないことが分かりました。

朝10時起床、12時にチームメイトと集まってご飯を食べて会場に到着しました。会場では選手とスタッフとの会話は英語だけしか駄目でしたが、スタッフ同士は日本語で会話していました。母語が同じなのにそれを使ってはいけないのはロールプレイング感があって面白かったです。

リハーサルが始まったあと、とりあえずD問題を通し（1ペナをしましたが）、その後は仕様の確認をしていました。python の scipy, numpy が使えなくて、数値積分が欲しいときに python を書くという選択肢が無くなりました。

ジャッジ結果を（too-late 含め）コンプリートしました。「MLE した場合 result がどうなるか」の clar を送りましたが、「冊子を見ろ」としか返ってきませんでした。冊子を見てもどうなるかは分かりませんでした。

ライブラリタイピングの練習をするときに、紙を（クリップなどを使いながら）ディスプレイに引っ掛けていたらスタッフにクリップの出処を詰められました。その後、ディスプレイに紙を貼り付けることが禁止されました。

チーム紹介で喋る人をじゃんけんで決めたら自分になってしまったので喋りました。我々の席がA-2だったので紹介が2番目で緊張しました。その後は解散し、tonosama たちと中華街の台湾料理屋に行き、赤コーダーと同じ空気を吸うことで赤コーダー力を蓄えました。

家に返った後ABCに出て 23時就寝。

day 2

7:00 起床、8:10 横浜着、チームメイトと合流して 8:40 に受付をしました。9:10 までに受付しないと失格になってしまうらしいです。

自分はしょぼんライブラリと蟻本、十数枚の白紙とぬいぐるみのぐんまちゃんを机の上に出しました。気づいたらコンテストが始まる時刻になっていました。

コンテスト

ebiさんがテンプレートを書くなどの準備をする間、自分がA、noyaさんがBを読みました。

Aは問題文を読むとDFSをすれば解ける、と書かれており、制約を見たらやっぱりDFSで解ける感じでした。実装を考えていたら、もっと軽いDP解が浮かんできたのでそれを書いてACしました（0:09）

noyaさんがBを書く間、残りの問題を見ました。ebiさんがDを見て何か気付いたらしいので聞くと、区間DPらしいです。確かに区間DPですが、[l, r) が (数字)+(+(文字)+) で書くときの計算量に困っていました。しかし (数字) が1桁限定ということに ebi さんが気付き、事なきを得ました。復元に自信なかったので、ebiさんに頼みました。

そうこうしてるうちに、noyaさんから B にセグメント木が必要そう、と言われたのでセグメント木を書きました。その後、たくさん通されていた F の考察をしました。この間にも D の実装が進みます。

Fは見た目は激難データ構造問題だったのですが、縦・横の 0・1 を map で管理することでいいと思い、実装を始めます。途中でバグっていたので B に代わってもらいました。Fのバグが分かったので、B が通った後 F を直しました。そして、問題文を誤読していて「黒の連結成分の個数」を数えていることに気付きました。数えるべきは「連結成分の個数」だったので、少し修正することでACを得ました。(1:06)

その後すぐに D も AC 出ました。(1:18)

ここで実装キューが解消されます。E は時間計算量 O(N 2^N), 空間計算量 O(2^N) がせいぜい限界です。要素を 1つずつ追加する bit DP で、追加できる条件を特徴付け、「だめ」の判定を高速に行えばいいと考えました。条件を整理したあと、高速ゼータ変換を使う解法が思い浮かんだのでnoyaさんに話すとよさそうとなり、実装をしました。

E がバグったので、noyaさんの K に代わりました。E は bit演算の | を || と書くミスをしていたのでそこを直すとACしました。(1:52) K もすぐに通りました。(2:16)

G が結構通されている確率 998 問題で、FPS に頭を支配されながら考察をしていると、天才 noya2 が「1回の操作で枚数がほぼ 5/6 ずつになるから、実は操作回数が少ないのでは？」と考察し、ほどなく「考えるべき状態数は少ない」という結論になりました。noyaさんが証明：AC をしようとコードを打ち始め、できたところで「間に合う」と提出してもらうと、離席しているnoyaさんの意思に反してTLEが出ました。自分が time コマンドで最悪ケースを測ってみると 5.7 sec と出て、間に合っていませんでした。帰ってきたnoyaさんと相談し、map を unordered_map に変えて測ると 3 sec となったので、投げると AC でした。(2:47)

H はフローっぽい見た目の上、通しているチームが「ちゃんと強いチーム」ばかりで、おそらく本当にフローだろうと思いました。一人のときは貪欲が最適であることはすぐに分かりましたが、二人のときが問題で、各人にとっての「最適な順序」が違うのです。この問題でフロー以外にありえるとしたら DP が最も怪しいですが、この性質によって DP はちょっと厳しそうということが分かりました。
フローは当初ラグランジュに頭を支配されていましたが、よく見ると燃やす埋めるで書けることが分かりました。dinic 法を書き、バグらせたところで J に交代しました。

H は最大流がバグっているのと、燃やす埋めるの張り方が間違っていたので直しました。サンプルが合ったので提出すると WA が出てびっくりしました。この時点で残り 1 時間です。

とりあえず J に交代し、残り H, J, できたら I まで通せたらいいと思っていました。ここで I を線型計画問題に直してebiさんに送りつけると、ebiさんはその線型計画問題を見つめていました。それはともかく H を通さないといけないので、H のバグ取りをしようとしますが、何が間違っているのか分かりません。

J を通そうということになりますが、TLE が帰ってきます。 H を通したいので noya さんと ebi さんが頑張ってデバッグする間自分は H を見つめています。 HLD、遅延セグ木があればよさそうということで、HLDをebiさん、遅延セグ木を自分が書きました。（残り20分）

shobon も H は諦めて J のデバッグを始めます。遅延セグ木にバグが 1 つ見つかり、HLDにバグが 2 つ見つかったので直し、残り5分で提出しました。提出結果が全然帰ってこないのでebiさんが定数倍高速化を行い再度提出しました。その後 AC が帰ってきて盛り上がりました。(4:55)

H はだめだと分かって提出しましたがだめでした。

その後

実はコンテストのチーム紹介文にnoyaさんが作った問題を載せていたのですが、台湾の国立陽明交通大学のチーム NYCU_FriedShrimp から解法を聞いてほしいと言われ、その解法は AC でした。なんと台湾のお土産に一之軒のパイナップルケーキをもらいました。ありがとうございます！おいしかったです！

解法紹介を聞くと、H はやっぱり最小カットで、解法も一緒でした。I は当初線型計画かと思いましたが、それは罠で天才数学バトルだったらしいです。

Yes/No は 3ninn_orannwa_boke のチーム名の読み上げが毎度面白かったり、kotamanegi_marunage の下剋上にびっくりしました。最後は Speed Star の単独全完で超盛り上がりました。

AMATSUKAZE は 8完13位、調子はよかったもののあと一段足りず、というところです。 H が通せば 10 位だったのでフロー大臣としての威厳が失われ落ち込んでいました。

"パーティー会場に行ってください、パーティーはもう始まっています！" そのアナウンスとともに懇親会が始まりました。食べ物がたくさんあり、いっぱい食べました。参加者の名札が全員本名で分からなかったので、結局tatyamさんのもとに固まってしまいました。

農工大の sankaKsu 、中央大の SSU が話しかけてくれてうれしかったです。ebiさんにインターンの資料をもらいましたが、いりませんでした。JAG から JAG の缶バッチをもらい、「引退したら JAG に入ってくれよな！」的なことを言われました。すでに JAG にいる人も JAG の缶バッチをもらっていました（？？）JAG には機会があったら行きたいと思います。

最後に余った食べ物（おにぎりなど）の配布イベントがありましたが、おなかいっぱいなので賞味期限が長いお茶だけ取りました。

ぬ〝

H のバグ取りを頑張り、後で通りました。方針は一緒ですが、本番中にデバッグしても 1 時間以上かかるレベルの呪いのバグでした。

ありがとうございました！

スタッフのみなさんにはとても感謝しています！このような大きいコンテストはずっと続いて欲しいと思いました。

P.S. 明日は関数解析の試験がありますが、テスト勉強どころか休んだ分の授業すら追えていません。

P.P.S. 関数解析の試験は1問も解けませんでしたが単位は来ました。