JOI 2022/2023 春季トレーニング参加記

atree というハンドルで競技プログラミングをしています。JOI’23 の春季トレーニングにボーダー通過して参加してきたので参加記を書きます。

Day 0

東大の安田講堂で表彰式をした。当学の学生でもなかなか入れないなどと聞いていたのでラッキー。~~司会がグダっていて少し残念だったが…~~ 表彰式後は交流会ということで、それなりに交流できたので満足。筑駒の輪の中に入ったときにパ研に競技プログラマが絶えない理由を聞いてみると、E8 さんが競プロをしていない人間を追い出していたためとのことで笑ってしまった。非春合宿勢とはあまり喋れなかったかも。

春合宿参加者は早めに抜けてプラクティスへ。参加者が筑駒勢で飽和しているので迷うことがない。エディタは VSCodium を使おうと思っていたが、思いの外自分が Vim key bindings に依存してしまっていることに気付いたので、Vim で書いて Clangd をインストールできるVSCodium をフォーマッタとして使うことにした（最終的には Vim 単体で書いていたが）。

Day 1

6時起きで辛いが、遅刻はせずに済んだ。行きの電車の中ではポインタ木の実装と焼きなましを確認していた。交流会で人が「Li Chao Segment Tree は書けるべき」と言っていたので確認したが厳しそう。競技会場は長机に椅子二つで一人分だったが、隣のぷらにゃは右側の椅子でコーディングして左側の椅子で考察をするというスタイルをとると言っていて、これをマネすることにした（彼は yuto1115 スタイルと呼んでいた）。チューターであるところの yuto1115 先輩は遅刻…

Currencies

木クエリでなんとなく嬉しい。手元で実験をしていると銀貨は C の昇順で Greedy に使えばよいので小課題 1 は愚直に通る。小課題 2 は C 共通なのでパス上の関所の個数がわかればよくて、これは木上の imos 法で計算可能。少し LCA(Binary Jumping) をバグらせてしまった。小課題 3 はパスグラフで、これが解ければ一般の木でも HLD で解けそうとはわかるものの 30 分くらい悩み続ける。すると Pararell Binary Search で解けることに気付くのだが、結局バグがとれず小課題 3 も通せずに終了してしまった… みんな典型だと言っていて、自分が春合宿で満点を取れるギリギリの難易度って感じだったので悔しい。

自分の方針だと HLD + Pararell Binary Search + Fenwick Tree で $lo g$ が 3 個付くのが微妙で、HLD を Euler Tour にして頑張る人が多かったらしいが、別に $lo g^{3}$ でも通るとのことでぷらにゃが PCT に早口でキレていた。

Festival2

入力定数個の mod 数え上げが JOI で出て笑ってしまった。順列全探索だけ書いて終了。（小課題 2 もうまいことやればできそうという感じではあったが Currencies の方に時間を使ってしまった）

Passport

とりあえず三乗の区間 DP を書いて 16 点。これを Segment Tree で高速化して終わってしまった。

昼食は崎陽軒のシウマイ弁当。はんぺんさんと低得点のなぐさめあいをしていたところ、横では kaage が「最下位！笑」「今までで一番冷えた日」などと叫んでいた。彼は毎日これを叫んでいたと思う。自分は 38-5-22 で 19 位。ボーダー通過の自分にとって順位としては悪くないが、Currencies の悔いが残る。

Currencies の解説は ynymxiaolongbao さんだったが、初めてハンドルの発音を知って感動した。Festival2 はやはり激ヤバ枠だったらしく、自分は DP から置いていかれてしまったものの、最後の方は任意 mod NTT or Karatsuba 法 + offline/online 変換みたいな感じで苦笑いだった。終了後は万年筆を貰って帰宅。ABC はサボって就寝。

Day 2

Conveyor

Communitcation なのでとりあえずは無視していたが、後から考え始めた。 $N = 2$ はさすがに自明だが、それでも配点が 1 点しか無くて泣いてしまった。 $N = 30 (= Q)$ を考えていると、葉に置けばその葉と接続する辺の向き付けが決定できることに気付く。以降のクエリでは、葉から出る向きを設定しておけば擬似的に葉を削除したことに対応するので、葉を削除 → 葉になった頂点を enqueue するみたいな方針で実装した。全ての葉で同時に操作してもよいが、バグりそうだったので一つずつやることにしたものの、結局かなりバグらせてから 15 点。小課題 3 は $N = 100000$ のパスグラフだがパッとはわからずに終了。結局 $mod 3$ で置くと上手くいくとのことで、天啓が典型系だなあなどと感じた。解説が noshi さんだったが非常にわかりやすかった。天才パズル系だがキレイな解法で、4 日間のセットのなかでも好きな方の問題だった。

Mizuyoukan2

とりあえず $O (N^{3})$ の区間 DP はできて実装した後、セグ木で $O (N^{2} lo g N)$ にするのに添字ゲームをした。見た目が激ヤバなのであまり考えなかったが案の定だった。谷の長さを 1 としてよい考察くらいは気付きかったが…

Council

愚直は書いたものの、小課題 4 以降がなかなかわからない。 $M \leq 2$ まで書いて終了。見た目が簡単なのでもっと得点したかったが他の実装に時間をとられてしまい、あまり考えられなかった。

15-22-15 で 22 位。冷えてしまった。Day 1 の反省から自明部分点をこぼさないことを意識したが、逆に考察してやっと通したみたいな部分点が無くてなんだかなあと言った感じ。海浜幕張に直行しクラスの打ち上げに参加してから帰宅。

Day 3

15 分ほど寝坊してしまい激焦りしたが、結局いつもより早く家を出れた。朝は Euphoria を聴いて士気を上げる。そろそろ OutputOnly が出そうとの評判なので朝は焼き鈍し法の確認をしていた。飲み物はぷらにゃが激推ししていたキャラメルミルクティーを選んだが、甘すぎた。おれはもう若くないんや…

Chorus

ARC っぽい単純な設定だが自明部分点はなさそう。少し考察すると、最小値以下は全て達成できるので最小値さえ求めるアルゴリズムを考えれば全探索できそうで、これは Greedy でよいことが簡単に示せて $O (2^{n} poly (n))$ 。隣接 swap による編集距離が Greedy でよいのは未証明だったがそれらしいので実装して 16 点を得た。解説を聞くと DP にしてから高度典型知識で高速化みたいな感じだったが、自分は DP にさえたどり着けずに撤退。解説が maroon さんでびっくりしていた。

Cookies

小課題 2 までは DP でよいのでそれぞれ実装したもののなぜか通らない。手元で hack できないので出力形式を確認したりしていたが、結局わからずじまいで終わってしまった。解析中にテストケースを見ておくべきだった…

Tourism

もう一回木クエリが出た。今度こそは解きたいと思って時間をかけたが、結局小課題 3 以降はわからず。 $O (NMQ)$ の小課題 1 を bitset で高速化して小課題 2 を通してしまったので、これに味を占めたのか以降もこれの高速化を考えてしまった。 $C_{i} \to C_{i + 1}$ で通る頂点集合の bitset を Segment Tree に載せる方針だったが、よく考えればこの時点で既に $O (NM)$ -space になっていた。あのですね… $C_{i} \to C_{i + 1}$ で通る頂点集合の部分は、HLD の head に heavy path 上の頂点集合の bitset を載せるみたいなことをしていたが、最初に head に辿り付くまでは愚直に頂点を追加していくのでパスグラフとかで終了だった。うーん。

16-0-17 で 23 位。全部難易度 11 っぽいものの全体的に失敗してしまったので、自分今まで何してきたんだろうなあなどとブルーになってしまった。特に Tourism は冷静な考察とは程遠い状態だったので反省した。3 日目にもなって少しダレてしまった自覚もあって、反省点を確認しながら帰宅。

Day 4

高校の競技プログラミングの総括だと思って緊張感を取り戻した。 mendako さんと喋っていたところでチューターの square1001 さんに意気込みを訊かれたので、一問くらいは満点をとりたいと応えるといつもの調子で「いいですねぇ〜」と言ってもらえた。

Battle

問題開いて一問目が「最後の戦い The Last Battle」でアツい。弄られる系の Communication のテクとして、過半数を支配するというのを覚えていたので盤面を 4 分割する方針はすぐ生えて 11 点。結局他の問題に時間をかけたのでこれ以上は進まなかったが、斜め領域で分割する応用は気づけてもよかったかなあ。

Guard

一回流し読みしただけでは問題文が理解できなくて、少し考えても小課題 1 さえわからないので激ヤバ枠だとすぐにわかる。ちょこちょこ考えていて、おそらく全体で 45 分くらいは使ったが、なにもわからなかった…

Travel

自明小課題の配点が比較的大きいため JOIG との共通枠だろうと思って時間をかけることにした。小課題 3 の $X_{i + 1} - X_{i} \leq 100$ の意図がわからない。30 分ほど考えていると、移動するごとに移動済みの区間は少なくとも 1 広がっているので $k$ 回動いた後は片側の長さが $k$ 以上になっていて、観光地間の距離の上界だけ動けばそれ以降の移動は単調になっていることに気付く。天才！これで小課題 3 を通して 45 点。

次の小課題（満点）が 55 点なのでビビってGuard の小課題 1 に移ろうともしたが、square さんに言った意気込みを思い出して満点を考えることにする。同じ方向に移動する部分を纏めることができればよさそうな雰囲気を感じて、折り返しの回数が最大になるようなケースを考えてみる。これには $0 \to 1 \to - 1 \to 3 \to - 3 \to \dots$ の平行移動などが該当するので、 $k$ 回折り返したときの区間幅は $Ω (2^{k})$ で抑えられる！（なぜか当時の自分は奇数の和のノリで $Ω (k^{2})$ だと勘違いしていたが…）

この時点で残り 90 分。スタート地点が観光地でない場合、最初の移動は最近観光地へ向かうのでスタート地点は $X$ のいずれかとしても問題なくて、観光地 $l, l + 1, \dots, r$ に移動済みで観光地 $i \in {l, r}$ にいるときのみ考えればよい。ここから左に動く条件は $X_{i} - X_{i - 1} \leq X_{r + 1} - X_{i} \Leftrightarrow 2 X_{i} - X_{i - 1} \leq X_{r + 1}$ なので、 $2 X_{i} - X_{i - 1}$ の Range Max Query ができれば左限を二分探索できて、右側も同様。セグ木上の二分探索も Sparse Table も実装に慣れておらず、制約を信じて $lo g$ を 2 つつけてセグ木上二分探索をする。off-by-one に苦しんだ末、終了 5 分前にサンプルが合うので提出。ソースをグッと睨んでバグを探しつつ提出結果を確認すると AC できていない。諦めそうになるが、それでもあがきながら終わりたいのでソースを睨み続けるとなんと max と min を typo していた！コンパイル可能であることだけ確認して信じて提出。

提出を受理しました… コンパイルしています… 実行・評価しています… 実行・評価完了！淡い緑色を背景にして 100 / 100 が表示され、思わず立ち上がりそうになって机をガタっと鳴らしてしまった。終了 90 秒前の劇的な展開に興奮しながら 4 日間の競技が終了した。

この日は 11-0-100 で、総合 261 / 1200 点の 21 / 29 位。やはり Travel は今回の春合宿の中でも最易枠だったようで、17 人が満点をとっていた。それにしてもあの淡緑色は見る麻薬みたいなもので、マジでヤバい成分が脳で分泌されるのを感じた。Travel は唯一の難易度 9 になりそうで、競技前の宣言は達成できた。

難易度 9 以下は満点取りたいなあ（出るのか？）
— atree (@atree4728) March 18, 2023

総括

自分は高校二年生なのでこの春合宿を期に競プロは小休止で、受験に移行しようかと思っています。高校受験してから競プロに本格的に取り組み始めたのでコミュニティがだとか、周りの能力に引け目を感じて悩んだとか、相手のレートに畏れずコミュニケーションをしようだとか、自分は代表争いなんてもっての外だったが春合宿で代表争いする競技性・戦略性がだとか、そういったポエムを書こうかと思ったがやめておきます。

チューター・JCIOI・作問担当・その他全ての JOI 運営に携わっていただいたみなさんには感謝してもしきれません。非常に貴重な体験になりました。

終わってしまった　最高だったなあ pic.twitter.com/b7WGyRJUrl
— atree (@atree4728) March 22, 2023

おまけ : ソラ書きを練習したアルゴリズム集

Segment Tree
- お手軽非再帰 Segment Tree の書き方（tatyam）
- 非再帰でもそんなに実装が重くはならない。
- セグ木上二分探索は覚えていなかったが覚えて損は無いと思う。
- 小課題を取るのによく書いたので優先度は高いと思う。
遅延伝播 Lazy Segment Tree
- noshi91/Library
- 信頼できるライブラリを選ぼう！
- 結局一度も使わなかったが、確実に遅延セグ木の理解は深まったと思うのでまあ。
  - 配列を 2 べきにしなくても OK の件とか
- 双対セグ木も自動的に書けるようになる。
Lowest Common Ancestor
- 練習はしなかったが、セグ木並に書いたので
- Binary Jumping か Euler Tour + RMQ かだが、自分は前者で書いていた。
Heavy Light Decomposition
- NyaanNyaan/Library
- ABC269H AntiChain 解説の前半部
  - コードは一部バグっていると思う
- 意外と軽くて、便利なので他に比べると高度だが優先度は高いと思う。
Centroid Decomposition
- ABC291H Balanced Treeで出たのでついでに覚えた。
- NyaanNyaan/Library
- 高難度木問題を解くテクニック集（tatyam）
- 安心と信頼の tatyam 神いつもありがとうございます
- 種々の実装方針のなかでもこのスライド中のそれが楽だったのでオススメ
Sparce Table
- 練習していないが、練習しておけばよかったと感じたので
- JOI では $lo g$ 一つが命取り！

atree4728

Table of Contents