A,B,C を全て読む。全ていまいちピンと来ないのでとりあえず A に着手する。

A は見た目がかなり異常で始めかなり手が付かなかった。全て高々 1 回しか登場しないは自明で 2 回しか登場しないもスイッチを 2 回登場するものに 1 個ずつ割り当てるとよい。4 回しか登場しないはこの流れだと 4 回登場するものにスイッチをいくつか使いそうだが、2 個だけだと上手く行かない。そこで、完全二分木状に 3 個使うと上手くいった。3 回登場する場合はどれか 1 個を完全二分木の根に向けることで解決した。

この解法が見えると同時に全体でスイッチを 2N 個まで使える解法はすぐ浮かぶ。ここで N = 16 でスイッチを 20 回まで使えるという小課題を見る。5 回登場するものにはスイッチを 7 個使ってしまうのでこのままだとスイッチの合計数を超えてしまう。だが、そもそもトリガーごとの移動先を別のスイッチ群にする必要はない。これを纏めることで N = 16 でもスイッチの個数を 15 個に抑えることが出来る。

さて、ここからはスイッチの個数を 2N 個から N + log N 個に抑える必要がある。だが、今の回路をよく見ると両方の行き先が二分木の根に向けられている意味のないスイッチがいくつか使われている。これらのスイッチを消すことで個数が抑えられるのでは？と思い出来るだけ葉のスイッチのうち意味のあるものを左から順番に割り当てることにした。個数の解析は分からないがそれっぽかったので投げてみると 100 点を得た。

C は割と見た目は一般的である。1 クエリ当たり O(N) で処理するのは stack テクを使えば簡単にできる。H_i <= 2 も H_i = 1 である区間をどれだけ長く取れるか？なので何をしても解ける。H_i <= 20 がセグ木に乗りそうだったので考えてみると、その区間の H_i の最大値や左に高さ x の山を付けたときに全員その山に移動するのにかかるコストの合計や、ある山に集まったとき、その左右での H_i の最大値が (x,y) の形をしているときのコストの総和の最小値を持てばマージ等が出来る。ここで (x,y) と書くと状態数が 20^2 通りありそうに見えるが、x,y のどちらかはその区間の H_i の最大値を取るので 1 ノードが持つ情報は O(max H) 個である。実装して 60 点を得る。100 点は割と考えたが歯が立たなかった...

B を考える。こちらもよくわからない見た目をしている。とりあえずいずれかの最短路上の頂点か辺が 1 個欲しいところである。二分探索をすると辺が 1 本得られそうなのが分かった。(このとき思いついたものは嘘だったが、嘘が発覚したときに考え直すといずれかの最短路上の辺を 1 本得る正しい二分探索が得られた。)

木のときはここからは簡単であり、得た辺を u-v を結ぶ辺とすると u 側の頂点に対して u からの距離で並べて二分探索を行うことが出来る。(頂点 x 以降の辺は u を根としたときの親に向かう辺を 1 に、x より手前の辺は 0 にとすればよい。) v に対しても同様に処理すれば 3 * log N 程度のクエリ回数で収まりそうである。

一般の時は u,v からの距離で bfs 木を作ればよさそうなのでそれで実装してみると 100 点を得られた。