ICPC 2023 Asia Yokohama Regional 参加記（Nzt3 視点）

11/25,26に横浜産貿ホールで開催されたICPC 2023 Asia Yokohama RegionalにNzt3,Sotatsu,otoshigoのチームacidrainで参加し、7完23位だった。

チームメンバー

Nzt3(私): 23B C++ 何を担当しているんだろう？
Sotatsu: 22B Python 構文解析担当
otoshigo: 21B C++ 幾何担当

国内予選

参加記があります

Day1 集合~リハーサル前

13-14時に受付をするという話だったが、「13:30にはほとんどのチームが来ている」という情報があったので13時ちょうどに集合できるように移動する。

中華街で何か食べるか→人多すぎ、他で食べる

12:50に会場前に3人とも集合する。時間があったので山下公園で海の写真を撮ったりする。
会場に着くと、AMATSUKAZEなど数チームがドア前で開場を待っている。Bocchi The Techも開場前にくる。開くのを待って受付をした。

acidrainは入口すぐの席が割り当てられていた。Tシャツと名札を入手して写真撮影をする。

コンテストルールとスケジュールとチーム紹介冊子を手に入れたので読む。
チーム紹介にAAを描いているのがいくつかと、問題を出しているのがいくつかと、非ASCII文字を書いているのがいくつかあった。

始まるまで時間があったのでType-Cの紹介文を読みながら持ってきたライブラリの確認をしていると、誰も木の分解を持ってきていないことがわかる。

開会式が始まるっぽいので待っていると、オープニングムービーが流れる。自分のチームがこれに載るのは初めてなので嬉しいね。

開会式で西崎先生が色々な話をしていたけど、Tシャツの色で階級が分かれていることしか覚えていない。
環境の使い方講座を受ける。

リハーサルコンテスト

休憩を挟んでリハーサルが始まる。
Nzt3はテンプレと環境作りの担当なのでVSCodiumを起動していつものを書いて動かしてみる。事前に試していなかったのでコンパイルオプションの名前指定が効くのを初めて知る。
とりあえずAのAC解法を書いて、一部を変えてWAにしてから提出してみる。CEが返ってくる。書き換えてから保存せずにコインパイルして実行していたので書き換え後にコンパイルが通らないことに気づいていなかった。自動保存の設定を入れる。
コンパイルだけ通るようにして提出する→WA 予定通り。
修正して提出する。→WA あ、書き換えたところを戻し忘れていました。 AC
SotatsuがBをPythonで書き、Nzt3とotoshigoがCを読む。→Cは練習の時にSotatsuが担当した問題だった。今日はotoshigoが書く。
BをACしたので記念にACコードを印刷する。
Cのサンプルが通らない。
印刷してSotatsuとotoshigoでバグ探しをしている間にNzt3はDを実装。
Cの原因を特定できたらしいのでPCをotoshigoに渡す。その間にDについて「判定は線形でやりたくない？」「2乗でも通るよ」「2乗でやるかー」などの会話をする。
Cが通ったのでNzt3がDを実装し、提出。→WA x軸が一致する場合を見逃していました。 AC
インタラクティブのC++での練習もしたいよね。Bを書きます。ローカルテスターを動かせた。よかった。
リハーサル終了

USキーボードに慣れてなさすぎてタイピングが遅すぎる。キーボードを買って練習しておきたいね。(伏線)

チーム紹介

英語を話したくなかったので「先輩頼んだ！」をすると、Sotatsuがやることになる。
スライドはNzt3が作ったから適切な役割分担だな！
Sotatsu「We will solve all tree problems!」
すごい宣言をする。

Day2 集合~コンテスト前

全員が予定通りに起床し、8:30には会場に集合する。
開場してすぐ受付し、荷物からライブラリや飲み物など必要なものを取り出したら配布された袋に入れて封をする。

開始20分前にはトイレなどを済ませた。
開始5分前の案内でトイレ行く人がめっちゃいたように見えた。それだと開始に間に合わなくない？

コンテスト

Nzt3:環境構築+テンプレ写経 → C以降を読む
otoshigo:Aを読む
Sotatsu:Bを読む
VSCodiumの設定を終えてテンプレを書きおわりotoshigoにPCを渡す。
Cは998数え上げ、DはBNFが見えるので構文解析かと思ったけど読み進める前にotoshigoに質問を受ける。
otoshigo「このエラーわかりますか」
Nzt3「わかります(天下無双)」
修正して提出する AC
SotatsuがBで詰まっていたので問題概要を聞くと、平均値がp/q以上になる区間を知りたいらしい。
いつもの平均値を総和にするやつで解けるか考えると解ける。Nzt3が実装し提出 AC

順位表を見てFを読んでいたらしく概要が共有される。
Nzt3「違う色が隣接するところを……(考察の初手を垂れ流す)」
Sotatsu「解けました」
Sotatsuが実装し提出 AC

Nzt3,otoshigoがそれぞれG,Eを読み、共有。Eの2^N M くらいの解法が生える。

順位表を見るとDが通っていたのでotoshigoが読み、共有する。
Sotatsu,otoshigoによれば区間DPで解けるらしい。
otoshigoが実装する。
Nzt3「念の為大きいケースもやってみましょう」
出力 100(a)
Nzt3「良さそうですね」
otoshigo「出します」

WRONG ANSWER
なぜ？otoshigoがコードを読んでバグを探す。

その間にNzt3,SotatsuでKを考える。
直線 x=k で聞くことにする。答えが正になるようなkが2つ得られれば三分探索で中心のx座標と半径が求められる。
よく考えると、そのようなkが3つ得られれば数学的に中心座標と半径が求められる。
y軸にも同様にやることでクエリ1004回で答えられそう。
Sotasuが実は2つで良いことに気づいたので実装する。

otoshigo「(DのBNFを見ながら)これって数字は1桁ですか」
そうじゃん。
よく問題文を読むと、

Note that numbers of repetitions are specified by a single digit, and thus at most nine

と書かれている。さっき読んだ時はこんな文は書かれてなかった。
文字列長の約数のうち9以下のものだけ試せばいいね。otoshigoが書き直す。
WRONG ANSWER
どういうケースで落ちるかはわからなかったけど繰り返し回数を全探索できるので全探索するように変更。
Sotatsuが渋い顔をしているが、提出。
AC

ここらへんで弁当と追加の飲み物が配布されるが、食べる余裕はない。

SotatsuがKをPythonで書き上げて提出する。
WRONG ANSWER
小数処理のミスだったので修正して提出。
WRONG ANSWER
Nzt3,Sotatsuでコードと睨めっこをすると、ミスが見つかったので修正。
floatでroundを使っていれば通るやつっぽく見えてきた。
修正して提出し、AC

otoshigoがGの考察を進め、操作回数が少ないので解けることに気づく。そのままotoshigoが実装。
サンプルが全部あったのでTL確認のためにN=300000を手元でやる。
大丈夫そうじゃない？提出。
TIME LIMIT
手元で時間を測ってみると7secくらい。std::mapをstd::unordered_mapにすれば通りそうなので書き換えて提出。AC

残り20分くらいで少しでも考察が進んでいるのはEだけ。最後にこれを通すことを目指す。
とりあえずNzt3がM 2^NのTLE解を実装している間にSotatsu,otoshigoで考察を進める。
Nzt3がTLE解を書き上げたので提出する。←？
Sotatsuが判定部分の高速化を生やしたらしいので結果待ちの間にそれを共有する。
AC が返ってくる。←？

あと10分で考察が進んでいる問題はもうない。Jが木の問題だったので最後にTLE解だけでも出せないかと思ったけど何も生えない。

終了

コンテスト後

解説を聞いて初めてB問題のcの制約が小さいことに気づく。

acidrainは凍結後に3問通していたので3回Yesで凍結時の34位から23位に上がる。他の東工大チームが強い。7完爆速であれに並びたかった。

LegalOn Technologies賞としてUS配列のキーボードを頂いた。ありがとう！(伏線回収)

懇親会

スポンサーのブースを回ったり、他の東工大チームと集まったり、JAG合宿ぶりにあった他チームと話したりしていた。

スタッフも含めた東工大勢で集合写真を撮った。

おまけ

first print 賞は acidrain でした
— tatyam (@tatyam_prime) November 28, 2023

最初の印刷らしい。