読者です 読者をやめる 読者になる 読者になる

AGC 014 F Strange Sorting

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座標は数列の値です。

すると下図のようになります。

f:id:yosupo:20170512075557j:plain

すると、"一番左の列の点たちを適切な位置に動かす"を繰り返すような操作になることに気づきます。 具体的には各点について、「自分より上の点について、自分より左の列から移動してきたような点」が存在しない列、のうち最も左側に動きます。

操作をすると下図のようになります。

f:id:yosupo:20170512075548j:plain

ここで、上の点にしか移動が依存しないことを考えると、上から点を追加していく方針を考えたくなります。

要するに、各列について、その列に来た点のうちもっとも左側から来たものとの距離、を持って、その配列を管理しながらいい感じに処理をします。

各点についてどのような処理をするかというと、「配列の値 <= 移動距離」となるなかで最も近いものに移動し続けることになります。

もちろん愚直では間に合いませんが、ここで、配列の値が広義単調減少であることを利用します。

大体配列の値ずつぐらい移動することを考えると、今のいる場所の配列の値で平方分割することを考えたくなります。

具体的には「今いる場所の1マス先の配列の値」がsqrt以上かどうかで場合分けをすると、大きい間は愚直にバイナリサーチ、小さいとまとめて一気に動く、という操作を行えば良くなります。

計算量はO(NsqrtNlogN)と見せかけてO(NsqrtN)です。