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

noya2 です。AMATSUKAZE というチーム名で参加しました。結果は 13 位で、そこそこの順位でした。うーん、悔しいけど。

チームメイトの 2 人が既に詳しい参加記を書いてくれているので、こちらもぜひご覧ください！

自分はあっさりめに書こうと思います。

メンバー

ebi_fly (M1)
- 構文解析の王w
shobonvip (B3)
- フローの王w
noya2 (B2)
- 幾何の王w

王はおいておくとして、得意分野が分かれていそうだったので、チーム練習の時もそれぞれがといた問題の分野も自然と分担できているようでした。

ebi_fly
- 構文解析全般
- 木の問題の重実装
- DPの構築
shobonvip
- 天才フロー問全般
- DPの高速化
- ライブラリのタイピングゲーム
noya2
- 幾何全般
- 木の問題の考察
- 数学問、構築問とか

コンテスト前

TTPC2023 の準備で忙しく、本格的に練習が始まったのは本番 1 ヶ月前です。

コンテスト時間が 5 時間ということもあり、授業がある平日には時間が取れなかったので、主に週末の昼間に練習の時間をとりました。やったこと　:

Universal Cup (2nd Season)
Asia Yokohama Regional Contest 2016~2022 年分

day1

時間通りに全員集まり、会場近くで昼食を取りました。会場に着くと多くの参加者が既に集まっており、社会性であることだなぁ、という感じです。会場では公用語は English ONLY とのことなので、頑張って英語でスタッフとコミュニケーションを取ります。意外といけます、相手も日本人なので。

リハーサルでは初めて触る CLion というエディタを使いますが、補完の利き方が普段使っている VSCode と違う以外はそこまで気にならずにコーディングすることができそうな感じでした。リハーサル用の問題は

A 自明、ジャッジ練習用
B インタラクティブ練習用
C 呪われている見た目の問題、慎重になる用
D 実は間に合う系、びっくり耐性用

でした。D問題は自分が過去に解いたことがあったので、Cがそうであった shobon さんと交代して自分は C 問題を見ることにしました。 ebi さんには開始直後に環境構築とテンプレートタイピングをしてもらいました。

すべてのジャッジステータスを出し、 Clar を投げ、キーボードに慣れ、リハーサルは終了です。

day1 終了後はチーム tonosama と中華街で夕食、美味しかったが料理名を覚えておらずです。ルーロー飯のお友達っぽい名前でした。

ABC330 に 60 分だけ出てすぐに就寝。本番楽しみ〜！

day2

全員が起床成功、　会場入りを済ませたらすぐに競技が始まりました。

予定通り ebi さんが環境構築とテンプレート写経、 shobon さんが A 問題、 noya2 が B 問題を見ます。

臨場感が欲しいので、ここから常体

A はすぐに　AC ですごい。

B はシュミレーションだが誤読しそうで怖い、実装するも頭がバグっているため、全然サンプルが合わない。

Dの考察が終わったようなので一旦交代、セグ木で落ち着いてやろうとなって頭の整理が終わる。Dの考察ミスが見つかってPCが空いたのでセグ木を書く。といっても、ライブラリはほぼすべて shobon　さんに写経してもらっているため、 min_left まで必要ですと伝えてタイピングゲームをしてもらう。写経が終わりBの実装をし直したがまだ頭がバグっており、破滅。もう一度 D と交代。もう一度落ち着いて考えると min_left は必要なくなった、 shobon さんすいません。かなり実装を詰めて AC ! (30 分くらいバグらせていて、本当に良くない)

序盤で出遅れたので、とりあえず順位表に助けを乞う。 EFGK あたりが狙い目に見える、Fは解けているらしいのでまだ読まれていない E を見る。問題内容は単純で典型に見える。ただ $Θ (N^{2} 2^{N})$ を落としにきている制約に見えるので、なんとか $O (N 2^{N})$ にしたい。 shobon　さんと相談して高速ゼータ変換で条件をうまくまとめられると言われる、良さそうなので実装を任せる。このあたりで D と F は解かれていた気がする。

ebi さんから K が幾何&インタラクティブですとは聞いていたので、概要を聞いて自分の担当だと判断して取り組む。 ebi さんは木の問題である J 問題とフロー・LPに見える H 問題と I 問題に取り組んでいた。

そもそも円との共有点を持つ線分を引き当てるのに $500$ 回はかかる気がする。 $x$ 軸と $y$ 軸で独立に中心座標を計算するつもりになるとそれだけで $1000$ 回の質問回数を消費してしまい残りは $24$ 回、そうなるとそこから定数回で中心座標を当てる必要がありそう。よく考えると、 $2$ 線分が円と交わってくれていれば、円上の $3$ 点の相対位置がわかることになり、外接円を求める問題になる。そのためのライブラリを持ってきていたので慎重に実装して AC! インタラクティブ用のスクリプトが提供されていたので安心だった。

G はやばそうな見た目の $mod 998$ で、FPS的解釈を試みるも失敗、そもそもまともに解ける気がしない。shobon さんに modint の写経を任せて考察する。操作毎にカードの枚数が $5/6$ になることに注目すると操作回数はそこまで多くないように見えるので、PCが空いたところで実験をすると $60$ 回程度になると分かる。それなら単純な DP をメモ化再帰で回せばすぐに間に合うんじゃないか？ -> 実装すると間に合うっぽい。体感で TL の 5sec を下回っていたので提出し、一旦落ち着くために離席していると、全然TLEしていた。あほばか。 time コマンドで最大ケースに要する時間を測るとやや間に合っていない。 std::map を std::unorderd_map にして再度測ると間に合うっぽいので提出、AC！こういうペナが一番勿体無い、すいません。

この時点で ABDEFGK が解かれていて、残っている問題の中で勝ち目がありそうなのは HJ だろう、となり H は shobon さんに進めてもらい、 J は ebi さんと一緒に考えた。　H は正しそうな解法は既に生えており、実装もほぼ終わっているようだったが、解法が微妙に間違っているようでデバッグや再考察を要求されている。燃やす埋めるに帰着するらしいが、ここは shobon さんに任せることにする。

J は素直な木DPが 2 乗になって、全然嬉しくない。仕事の割り当てを考えると、いつもの条件（部分木内の仕事の個数が部分木サイズ以下）が浮かぶ。これを満たしながら貪欲に何かできれば嬉しい。そこでふと二日前の yukicoder で同じような考察をしたことがある気がしてきた。同じ操作を繰り返し行うとき、行う度にコストが増えていくという特別な制約がついていれば、できる操作のうちコストが小さい順に取っていけば良い、というものである。 $k^{2} = \sum_{i = 1}^{k} (2 i - 1)$ に直してこの形式に当てはめれば、部分木の条件を満たしながら貪欲に取っていく問題になるのでは？となる。証明はしていない。

とりあえずこの方針を ebi さんに伝える。HLDを書きたくないのでなんとか部分木クエリだけで済ませようと頑張る（後から思えばこれは悪手だった）が、実装しては考察ミスが見つかるを繰り返してしまう。部分木の条件を動的に管理する方法が正確にわからず（HLDと遅延セグ木を使えばできることはぼんやりと分かっていた）瞑想してしまって時間をロス、よくない話。なんとかサンプルを合わせて投げると TLE で、実験をするとまだ考察ミスがあった。残り 40 分程度で実装は重いが確実な方法を取ろうということで HLD と遅延セグ木を書いてもらった。HLD は ebi さんに、遅延セグ木は shobon さんに書いてもらった。その後の実装を全て ebi さんに任せ、自分はライブラリタイピングにミスがないかをチェックする。

ライブラリタイピングをするのは shobon さんがやってくれることがほとんどで、タイピングミスは書いた人がチェックするのが普通だったので、自分は全然慣れていなかった。結果として、「あっています」と宣言した部分に 2 つもチェック漏れがあった。目が節穴。すべてのミスを修正するのに 20 分くらいかかってしまい、提出がギリギリになってしまった。AC が返ってくるのにものすごく時間がかかったように思えた。まぁ通ったのでよし！

H は結局通せなかった。帰宅後に shobon さんが upsolve してくれた。

結果として 8 完 13 位。チームレートで言えば悪くない成績ではありそうだが、もっと上を目指していただけに悔しい結果に。完数はあっても解くのが遅かったりペナを出したりして、同じ完数の中で下の方になりがちで、今後があれば大きな反省点です。

ここまで臨場感

コンテスト後

コンテスト後は解説があったのですが、J問題の正当性をマトロイドで説明することができるようで、興味が湧きました。それから、YesNoはかなりの盛り上がりを見せ、特にSpeedStarの4時間ノーペナ全完は本当に感動しました。

表彰が終わると、その後はビュッフェパーティーということで隣の会場に移り、食事をしたり他チームや企業との交流を楽しみました。

終始 tonosama の potato167 さんと会場をうろついていました。慶応のチームや優勝したSpeedStarのSSRSさんと少しお話をさせていただくなどして時間を過ごしました。東工大がホスト校だったため traP のメンバーが数人アルバイトとして会場の整備や受付などをしてくれていたので、大大感謝を伝えました。本当にありがとうございます。帰り際に SpeedStar の Segtree さんに話しかけてもらい、競プロの精進方法について盛り上がりました。 traP には　traQ という closed でありながらサークル内では open なコミュニケーションツールがあるおかげで、オンラインでの交流が盛んで、これは競プロの精進においても便利なんです〜という話をしました。

上位チームに感化されて、もっと精進しなければ...！という気持ちになりました。今週は期末試験、え〜。

プレーオフ出場チームの発表はいつですか？

今後について

プレーオフに進出できれば、まだ先があるということになります。楽しみです。

ebi さんが今年で引退なので AMATSUKAZE は一旦解散か、 shobon さんと組ませていただけることになれば来年に向けて新メンバーを探すということになります。誰かいませんか〜。

さいごに

大会の運営陣の方、JAGスタッフの方、ありがとうございました！本当に楽しかったです！