AGC 014 Fを解きました。
解いた後に解説動画を見たら全然違いました。ゴリ押しです。
まず、数列を-1倍してよくある各点までのLISを求めるやつをします。 たとえば[3, 5, 1, 2, 4]ならば、[1, 1, 2, 2, 2]です。これは"初めてその値が高い項になるのは何回目か？"を表します。
サンプル3:[2, 10, 5, 7, 3, 6, 4, 9, 8, 1]に対してやると、[1, 1, 2, 2, 3, 3, 4, 2, 3, 5]となります。
ここで、LISといえばRank分けですね、というわけで分けると、[2, 10], [5, 7, 9], [3, 6, 8], [4], [1]となりますね。
ここで、実はこれをこのまま結合した[2, 10, 5, 7, 9, 3, 6, 8, 4, 1]を数列の初期値としても答えが変わらないことが示せます。略します。
で、これを二次元平面にプロットしてみましょう。x座標はLISの値、y座標は数列の値です。
すると下図のようになります。
すると、"一番左の列の点たちを適切な位置に動かす"を繰り返すような操作になることに気づきます。 具体的には各点について、「自分より上の点について、自分より左の列から移動してきたような点」が存在しない列、のうち最も左側に動きます。
操作をすると下図のようになります。
ここで、上の点にしか移動が依存しないことを考えると、上から点を追加していく方針を考えたくなります。
要するに、各列について、その列に来た点のうちもっとも左側から来たものとの距離、を持って、その配列を管理しながらいい感じに処理をします。
各点についてどのような処理をするかというと、「配列の値 <= 移動距離」となるなかで最も近いものに移動し続けることになります。
もちろん愚直では間に合いませんが、ここで、配列の値が広義単調減少であることを利用します。
大体配列の値ずつぐらい移動することを考えると、今のいる場所の配列の値で平方分割することを考えたくなります。
具体的には「今いる場所の1マス先の配列の値」がsqrt以上かどうかで場合分けをすると、大きい間は愚直にバイナリサーチ、小さいとまとめて一気に動く、という操作を行えば良くなります。
計算量はO(NsqrtNlogN)と見せかけてO(NsqrtN)です。
