ABC 401-500/ABC459F - -1, 1 - 競技プログラミング用 知識集積所

---

問題

ABC459F

必要知識

B以下レベルの内容は省略

• 考察問題
• ランレングス圧縮※

考え方

考察問題。
愚直にやっては計算量が大変なことになってしまうため、現実的な計算量で解ける問題に帰着させる。

まずは簡単なところ2つから。

1つめ、操作の順番は実は関係がない。
位置iで操作をした次に位置jを操作するのと、jの次にiで操作するのは結果が変わらない。
従って、操作順は気にせず、操作が必要だと判明したところから随時操作を行ってしまってよい。

2つめ、操作はまとめられる。
操作回数1回をコスト1とみなすと、問題に書いてあるのは「コスト1で、ある場所を-1して、その次を+1する」ということ。
これを位置をずらしながら繰り返すと、「コストkで、ある場所を-1して、そのk個後を+1する」ことができる。
コストkで「1」をk個右に運べると言い換えてもよい。

さて、2つの準備をしたうえで、本格的な考察をする。

まず、狭義単調増加というのが扱いにくい。
例えば、最後の1つ以外はいい感じに並んでいるのに最後だけ異様に小さい場合、前の方の全ての数から「1」を等しい個数ずつ最後の数まで運んでいくことになる。
このとき、狭義単調増加だと数列に全て異なる値が入っている状態であり、全ての要素から引き算する処理が非常に大変。
lazy_segment木※ならその処理も高速に扱えるが、しかしそれだと今度は「次はどこからどこへ「1」を運ぶのがよいのか？」の判定などの処理が大変になってしまう。

そこで、問題を「Aを広義単調増加列にするために必要な操作回数の最小値を求めてください。」に書き換える。
もちろんAの中身そのままでここだけ書き換えるのは問題があるが、同時に「Aのi番目の数からはiを引く」を実行すれば、きちんと同等の問題になる。

これにより、「最後の1つ以外はいい感じに並んでいる」というのが「同じ数が大量に並んでいる」という話になる。
つまり、データをランレングス圧縮※された形で持っていれば、広範囲から1を引くのも簡単になる。

さて、作り替えた問題も、まだまだ十分に考察問題と言えるもの。
今度は「では、「1」をどこからどこへ運ぶのがよいのか」を考える。
これは、端から考えるとうまくいく。（ここでは左側からやるが、右側からでも似たような考察はできる）

数列の左から順に1つずつランレングス圧縮※表現の数列に追加し、「とりあえず今のところOK」な形に整えていく。

これは、まず、そのまま追加してしまって問題ない場合は、素直にそのまま追加する。
そのまま追加するには数が小さすぎる場合、以下の手順で直前のランレングスブロックから追加予定のところに「1」を必要なだけ持ってくる。

最初に、直前のランレングスブロックから、2つ前のブロックと値が逆転しない範囲で最大何個「1」を持ってこれるか確認する。
それで追加可能にするのに足りる場合は、

• 全部から「1」を1つずつ運んでくる、を繰り返して、ギリギリまで迫っておく
  • 不足分をブロックの長さ+1で割って切り捨てた分だけ繰り返すことになる
• 不足が0以上ブロック長以下になったら、その個数だけブロックの先頭側から1つずつ運んでくる

とすることで、暫定最小コストで追加可能状態にすることができる。
足りない場合は、とりあえず運んできていい「1」を全部持ってくることで、ランレングス圧縮※のブロック合体が起こるので、その上で再度同じ判定を行う。

これを数列の左から順に1つずつ繰り返せばよい。
トータルコストは「1」を運ぶたびに逐一計上してもいいし、最終的にできたランレングス圧縮※のデータを本来の数列の形に戻してから改めてシミュレーションして求めてもよい。

解答例

解答例
（データを「左端、右端、値」で持っているが、「個数、値」でよかった……）

注意点

long long型を使用する。

Aが非常に長く、かつ左端にだけ非常に大きな値があるような場合、答えがint型からはみ出る。
また、コスト計算途中でもところどころint型では足りない部分がでてくるので注意。

別解