JOI '21 春合宿参加記

参加記

JOI '21 春合宿に参加しました。

~Day -1 (3/18)

2/27~3/18 にかけて JOI '20 春合宿のバチャを走る。Day 3 までかなりひどかったが、Day 4 の Capital City と Treatment Project がどちらも得意な問題で、満点。Legendary Dango Maker でも必死に点数を稼ぎ、なんとか代表ボーダーを超える。

えでゅふぉ 106 に出た。6 完。

Day 0 (3/19)

二重辺連結成分分解をしばらく書いていなかったので確認。旅行会社高橋君でダブリング LCA も一緒に練習。

SRM 802 があったので出た。Med で外れ方針を引いてしまって実装に時間がかかり、Hard の解法がわかったが間に合わず。赤復帰したいな

直後に茶碗蒸しさん writer の yukicoder に参加。D まで割と速く解いたが E の復元パートがわからず、撤退。

Day 1 (3/20)

全く眠れず、かなり不安になる。緊張のせいか誤って急行に乗ってしまい、渋谷に行き引き返すことに。会場に競プロ er らしき人が多く、ああ春合宿なんだなと改めて実感した。

問題を読むと、なんと最初から Output Only と書いてあるので、とりあえず後回しにして残り二問の部分点を回収する。IOI Fever の最初の小課題は N \leq 7 なので愚直に全探索し、2 点。小課題 2 は N \leq 14 なので、各国民の移動方法を 2 通りに絞り込むことを考えたが、よくわからなかったので、区間クエリが問われている Food Court のほうが得意そうだと判断。

小課題 2 は適当に愚直に管理すればよいので、すぐに解ける。小課題 3 は少し考えこんだが、加入する人数が少ないので脱退の人数も同様に少ないという典型に気付くので、客が並んでいる店舗の番号を set に入れ適当に二分探索し通す。小課題 4 は並んでいる人数を管理できればよいのは明らかだが、区間 chmax 区間 add クエリを処理することになる。Segment tree beats が必要と思い込み復習しなかったことを後悔し諦めそうになるが、beet さんの「セグ木に載せるモノイドまとめ」の記事に \max(x+a, b) の合成について書かれていたことを思い出す。伝播が必要な双対セグ木を書き慣れていなかったのでバグらせるが、なんとか通す。

小課題 6 は加入のみなので簡単そうだと思い、考察をすると各クエリで加入した人数を BIT に載せれば平面走査ができそう。BIT 上二分探索を書くのをさぼり log を二つつけたが、制約が小さく通った。小課題 5 を考察するが、なかなか解けないので一旦保留にし Aerobatics で適当に貪欲法を実装し 26 点。山登り法を実装しようとするが、最適化の対象が角度の最小値であるためかなり難しく、点数が全く向上しない。テストケース 1 だけはこれで最適解が得られていたので、これを提出し 28 点。Output Only は苦手なのでこれ以上は難しそうと思い、Food Court 小課題 5 に戻りさらに考察すると、小課題 4 と 6 を組み合わせれば解けそう。なんで 5 と 6 をこの順番にしたのだろうか。少し考えるとこれがほぼ満点解法なので、そのまま満点解法を実装することに。必要なデータ構造は既に書いていたので実装はさほど重くなく、若干バグらせるもスムーズに AC し、満点を得る。

IOI Fever でほとんど得点を得ていないので、小課題 2 を考えるも、全く解けない。感染しうる経路をグラフに帰着してダイクストラ法のようなことをする解法を思いつき、嘘かもしれないと感じるが実装して投げると、小課題 3 がなぜか通るが小課題 2 で数個 WA。反例が思いつかないのでランダムチェッカーを実装すると反例が得られた。小課題 3 の条件を満たす反例も得られたので、テストケースが弱かったのだろう。反例を回避しようとする方法を考えるが、何も思いつかずコンテスト終了。得点は 28-11-100 (Σ 139)。

昼食後に解説。IOI Fever の小課題 5 まで (37 点) はマンハッタン距離に注目した考察で解けると知った。これは取っておきたかったなあ。Food Court の満点解法は BIT 上二分探索をして log を落とすのが想定だったらしく、QCFium に犯罪と言われた。

帰宅。ABC196 があったので参加したら、18:12 で全完し 2 位に大差をつけて優勝してしまった。E で \text{clamp}(x+a, b, c) の合成が出題され驚く。もし Food Court が Day 2 に出題されていたらさらに何人か通していたのだろうか。Day 1 でよかった。とは言っても、Twitter で言及するわけには行かないので Discord で言及。F で大昔に走った Div. 1 バチャで出題された問題の類題が出題されていた。

Day 2 (3/21)

雨が降っていて、普段駅まで自転車で行っていたところを徒歩で行くことに。若干遅刻気味になってしまったが、駅から会場に向かっていたところなんと双子 (の両方) がいた。

問題文を読む。Escape Route の異常なクエリ数と変な入出力形式に驚く。Shopping が双方向通信の課題で嫌な気持ちになる。とりあえず Escape Route の小課題 1 は単純なダイクストラ法で取れるので、取る。不可能枠だと思っていた Road Construction の問題文を読み返すと、誤読に気付く。( K 番目までに小さい Manhattan MST を求める問題だと思っていたが、 K 番目までにマンハッタン距離が小さい点対の距離を求める問題だった。) 小課題 1 は愚直を書いて取り、小課題 2 は適当に優先度付きキューで取れる。小課題 3 は K=1 なのでマンハッタン距離の最小値を求めればよい。いかにも既出そうな見た目だが見覚えがなく焦る。少し考察をすると x でソートし y の小さい順に x+y をセグ木に載せればできそうなので、実装。小課題 4 の K \leq 10 は上位 10 個の数を持つセグ木で解けそうだが、定数倍が重そうなので後回しにし、Shopping を考える。

小課題 1 で L, R をそのまま送れずびっくりするが、 P を Bruno がそのまま送ってしまえばよい。小課題 2 を考えるも解けないので、得意そうな Road Construction に戻る。45° 回転させて二分探索をすると BIT を持ち平面走査をして K 番目だけが取得できそうなので、それを 10 回やれば小課題 4 が解けそうだが、よく考えるとマンハッタン距離が d 以下のものをすべて列挙することがセグ木でできるので、これで満点が取れそうと思い実装するが、小課題 5 で数ケース TLE し 32 (5+7+20) 点しか取れない。二分探索をしゃくとり法にしたり、配列を再利用するなど定数倍高速化をがんばって少しずつ実行時間を落としていくと、満点が得られた。

愚直解しか書いていない Escape Route を考え直すと、 T _ i=0 の場合に帰着させればよく、一日目については始点ごとに T の降順に処理すると実質 Bus なので実装すると 25 点。Shopping に戻って小課題 2 の考察。よく考えると (L, R) の組は 10^ 8 通りくらいしかないので、番号を付けその下位 18 bit を送ると Bruno にすべての候補についての答えを送ってもらうことができる。実装すると 10 点。小課題 3 は解けそうにないので Escape Route に戻り、微妙にアルゴリズムを変更したり定数倍高速化したりすると、急に 70 点になる。定数倍を詰めるも O(NM^ 2+ QN + Q \log Q) ではさすがに満点は得られなかった。得点は 70-100-10 (Σ 180)。

昼食で Shopping の小課題 2 で L をそのまま送れることを指摘され、驚く。解説で Escape Route と Shopping の満点解法を聞くが、よくわからなかった。

ARC と CF Div. 1 があるので、出る。ARC は赤になりたかったが、D の解法に気付くのがかなり遅れ、2767→2787 (+20) となった。E のペナが痛い。そのまま 10 分こどふぉった CF Div. 1 に出ると、なぜか 40 分くらいで D まですぐ解けてしまい、なんと 9 位で 2837→2954 (+117)。2950 タッチしてしまった。

Day 3 (3/22)

今日も Communication があったが、見た感じ最初のほうはそこまで Communication 要素はなさそう。とりあえず Meetings 2 の bit 全探索で 4 点と Ancient Machine の bitDP で 5 点。Bodyguard の小課題 1 は後ろから DP するのに気づき、6 点。Meetings 2 の 20 点はパスを固定すれば簡単に解けたが、満点は難しそう。Bodyguard の小課題 2 もすぐわからないので Ancient Machine 小課題 2 を考えると解法が生え、ランダムチェッカーを書いて確認。文字列を普通に伝えて 30 点、3 進数を利用して 5 文字ずつ伝えて 40 点。XZ の区間・Y の区間に分けてうまく情報を伝えると \frac{3}{2} N bit ででき 45 点、さらにそれを連続する 2 bit が立っていないことを利用し 4 bit を 3 bit で伝えると \frac{5}{4} N bit で 57 点。これ以上は難しそうだと思い Bodyguard に戻って図を書いてみると小課題 2 が解けそうな感じではあるが、斜線のまま考えていたため実装がとてもややこしそう。あまり頭が回らず、Meetings 2 の満点が解けないか、Ancient Machine の 70 点が取れないかなど考えているうちにコンテストが終了。57-6-20 (Σ 83) でかなり冷えてしまった。

解説を聞く。Ancient Machine の 70→100 には気づいていて、70 点解もさほど難しくなかった。Bodyguard も Li Chao Tree を書かせる満点はともかくその前の小課題 4 (48 点) までは解けたなあ。

Day 4 (3/23)

Day 4 も Day 3 のように冷えると代表落ちしてしまうので、それは絶対に避けたい。

Day 2・Day 3 と Communication Task が連続していたので今日こそはすべて Batch になると期待していたが、裏切られてしまった。とりあえず取れる部分点を探すと、Event Hopping 2 の小課題 2・3 が取れそうなので取る。さらに Worst reporter 4 の小課題 1 は単純な木 DP で取れそうなので実装。Navigation で L=5^ 7 を実装しようとしたところ、候補地は重複しないという制約を利用できることに気付き、 L=4^ 7+7\times4^ 6 を実装し 13 点。Event Hopping 小課題 1 に戻ると、DP の遷移を勘違いしておりただの累積 min で解けることが分かったので、実装。

Worst Reporter 4 の小課題 2 はいかにもマージテクを使いそうな見た目だが、累積 min を取る操作の扱いがややこしい。がんばって考えると、区間 chmax 区間 add の遅延セグ木をマージすれば解けそうなので、実装。木上マージテクのよい実装方法を知らなかったので HLD をするが、子を最初の子と swap するときに子を参照渡しにしていなかったバグになかなか気づけなかった。なんとかデバッグし、79 点。満点を取るために、さらになもりを連結成分分解し閉路部分を圧縮して木の場合に帰着する実装をしかなりバグらせる。最終的に 264 行の強実装となってしまったが、なんとか満点を取れた。

Event Hopping の満点よりも Navigation 2 で部分点を稼ぐほうが簡単だと判断し、 L=3^ 7 を実装し 19 点。さらに L=2^ 7 を考えようとしたが構築を考えている間にコンテストが終わってしまった。得点は 39-19-100 (Σ 158)。

昼食後、順位表を見ると 4 位以内に入っていそうで一安心。解説を聞く。Event Hopping はあまり考察できなかったが実は比較的簡単な問題だったらしい。だが、区間区間スケジューリングをダブリングで処理するという典型が完全に抜けていた。これ ACLC-D Keep Distances でもやられたんだよなあ。Worst Reporter 4 は実は DP の情報をうまく持つと map をマージするだけでできたらしい。終了後、QCFium に木上マージテクの実装は move や swap を使うとやりやすいと教わった。

総括

合計得点は 560 点だった。満点を取った三問はどれもセグ木を使ったので、セグ木の人だなあと思った。(解説前に双子などに話したらセグ木の人って Segtree じゃんと言われた。たしかに。) IOI Fever, Bodyguard, Event Hopping 2 など明らかに取れた得点を逃していたところが複数あり、まだまだだなあと感じた。