部分点１
問題文を読む
部分点２
各頂点から、直左右の自分以上の値を持つものにコスト１の辺を張ったグラフがあって、a~bの最短距離をQ回求めよという問題。
辺は遅延セグ木(max,max)とかで殴るととりあえず分かる。他に天才解法がありそう。
辺が2*N個なので、BFSとかをやるとO(NQ)
部分点３
わからん
満点
まず、辺をすべて上向きとみなし、左からのパスと右からのパスが合流する形にみる。
右からのパスは、左を過ぎない範囲で最左まで伸ばして、それを越えないように左からのパスを伸ばせばよい。高いところの辺ほど速いので、これが成り立つ。
いま、x始点のパス上にある~を過ぎない最左(右)の頂点とxとその距離がわかればよい。
クエリに対処するため、f(x,k):=xから距離kの中で最左(右)のもの という関数を考える。
この関数を愚直に計算するのはO(N^2)かかって部分点2と変わらないが、グラフの形が明らかに特殊なので、何かができそうなので、何かをする。
・出て行く辺は、左と右に一本ずつの2本である。
・すべての辺の重みが１のDAGである。
・高いところほど速い
・高いところはスルーされない⇄すべての辺は内包・外包関係にある
これらを眺めてエスパーすると、次の観察が得られる。
◯左と右を極めればさらに左と右を極められる
つまり、関数fは再帰関数である。
証明は背理法とかで頑張ればできそうだが、ACしたことを証明にしてしまう。
f(x,k,左)=f(x,k-1,左)とf(x,k-1,右)の左向きの辺のより左な方、右は逆となる。
これを実装すると一見O(NK)だが、おなじ深さでも辺は貼られているのでO(N^2)になっている。Virtual本番ではこれでTLEを連発して時間を溶かした。つらい。
改善が不可能に見えるが、座禅を組みながら中国人のコードを眺めると、この関数が結合律を満たすことがわかる。よって、ダブリングをすることでO(NlogN)で解けた。
分からなくて解説を見たが、解説が私の読める日本語ではなかったので、ACしていた中国人のコードを眺めて考えた。結果、最後の結合律にたどり着いた。TDPCで見た。深く考える前に、その前の貪欲に疑いを持ってしまったことが失敗。
考察過程は明らかに違うが、もしかすると解説とやってることが同じかもしれない。
