###### tags: 競技プログラミング ###### tags: 参加記 # JOI'22 本選参加記 JOI 2021 - 2022 本選に参加したので、参加記を書きます。 ## コンテスト前 予選で失敗して本選参加者 2 倍の恩恵を受けている、かつ春合宿は厳しいので、精進はぼちぼちという感じだった。 ## 本選一日目 人々の自己紹介映像が流れ、本名と顔が大公開されていてウケた。実際本名とハンネが結びつかないのでよくわからないみたいなところがある。 ABC に出る予定だったが、DoS 攻撃かはわからないが AtCoder が鯖落ちしてコンテストが無くなった。この前 B と D が入れ替わるインシデントがあったが、最近の AtCoder はこの感じのトラブルが無かったので新鮮（自分が始めたてのときに何回かあった気がするが）。去年は地震で本選自体が順延されたらしいので謎ジンクスが生えてしまっている…？ ## 本選二日目 コンテストは 9 時スタートだった。提出履歴からエスパーしていつものやつを書いておく。 - `9:00` 開始。直前でインターネットの調子が悪くて焦るが耐える。 - 普通に A から読んでいく。 - `9:11` 読むと座圧して累積和とってにぶたんと書いてあるので実装すると、AC。太陽回避で嬉しい。 - B を読む。 - `9:37` B も決め打ち二分探索と書かれているが、授業を $M$ 回までしか受けられないのに気付かず、コミュニケーションのタブを開きかける。気付いたので実装すると 0 点。え？ - `9:44` とりあえず適当にリファクタリングをしてお茶を濁す。二分探索でバグらせたときの一般的なテクニックを加えると 91 点。え？ ```cpp= auto ok = 0_i64, 1_i64; while(check(ng)) ng *= 2; ``` - `9:48` まさか…と思いながら`i64`を`u64`にすると 100 点。は？ - C を読むが問題文に答えが書いてないのでとりあえず D, E も通読する。 - C を考える。$B_i$ でソートして Greedy に見えるが、$N \leq 500$ なのに $\mathcal{O}(N^2 \log N)$ とかで解けちゃうので嘘っぽくて、実装したくない。 - D を読むと、部分点が C より取りやすそうなので考える。雑に辺を貼れば BFS できるので実装するが、index を `usize` で持っているためちょっと大変。 - `10:27` 提出すると 0 点。え？ - これ以上自明部分点に時間を割くと不快なので考察を進める。すると辺の貼り方を考えたときに行き先は連続した区間になっていることに気付くので左端・右端のみを持つようにすると実装が楽だね、になる。 - これ区間更新・一点取得じゃん→うしさんの双対セグ木ペタリ。 - `10:24` 提出。8 点。 - `u` からの遷移が `rep(v, l[u], r[u]) { ... }` の形になっているため、これもまた区間更新・一点取得だと気付く。`queue` に詰める頂点を探すのに愚直をするとその意味が無くなるので考えると、未探索頂点を `std::set` で持つとにぶたんできるので、削除しながら詰めればいいことに気付く。 - `11:13` 提出。27 点。 - ちょっといい感じなので執着して、自明枝刈り（`dist[t]` がわかったら終わり）と QCFium 法を試すがもちろん変わらず。とりあえず C に移る。 - `11:52` とりあえずさっきの Greedy を書く。10 点。涙。 - `12:00` 血迷って `nan` を提出してみる。0 点。バカ。 - `12:13` 満点わかりそうにないので bitDP で別の部分点 23 点を取る。 - D に執着したいが、E の部分点を取るべきなので `12:30` まで D を考えることにする。 - なんの成果も（略） - `12:49` E の自明部分点を取りにいく。0 点… - `12:55` こういうときは実装方針をスッパリ変えると良いことが一般に知られていて、9 点。 - `13:00` おわり。終了宣言されてないのに人々が Discord で喋り始めてびっくり。 - Zoom で解説してもらう。ひらきちさんのがおもしろかった。 ## 結果 100 + 100 + 33 + 27 + 9 = 269 で本選落ち。来年の本選は 80 人かもしれないので来年も本選に来たい。願わくば春に… ## 感想 初めての JOI、楽しかったです。各位ありがとうございました〜。