ABC 072 D - Derangement
Difficulty: 656
まず、O(N^2)以上の操作は不可能
また、最小回数を求めるために全ての場合を調べるのも指数時間かかる。（はず）
まずは実験
note1 4 3 5 2
1 2 3 4 5
x x
4 1 3 5 2
4 1 5 3 2
note9
1 2 4 9 5 8 7 3 6
1 2 3 4 5 6 7 8 9
x x x x
x に着目して入れ替えていくのがいいのか？
x はi = p_iとなってしまっているところを意味する。
これ以外のところに着目してしまったら余計に回数増えそうな気もする。
もしかしてDP...ではないか？
二つの場合は考えやすい
三つの場合は？
一つ一つ範囲を増加させて解くってことはできなくもなさそうだな
ただ、部分最適性が成り立つのか...？
不安になるポイント
xを目当てに揃えた結果、他のポイントで新しく x が現れないか？
どうだろ
そのような場合ってどんな時だ？
まず、 x が現れるとはどこかの i で p_i == i となることだが
ある j に注目して隣り合う二つの数をスワップした時に
p_{j+1} == j か p_{j-1} == j か p_{j} == j + 1 か p_{j} == j - 1 となるか？
となる場合が存在するか
これは存在しない
着目する j が必ず p_j == j を満たす。
順列 p は同じ要素を二つ以上持たないので、
p_{j+1} == j p_{j-1} == j
p_{j} == j+1 p_{j} == j-1
のうち一個以上でも満たすことはない。
よって、 x が生まれることはない。
つまり、操作を行うと必ず x が減る。
一個ずつ隣接せず x が並んでいる場合は
問題は x が二個ある場合とか、3個並んでる場合とか
p_j == j, p_{j+1} == {j+1}, p_{j+2} == j+2, ...
二個ずつ選んで操作するのが最適か？
p_j, p_{j+1}
最適みたい
一回の操作では高々連続した二個しか x が消えない
順列のうち二つの要素以外が変わることはない。
ので、仮に n 個連続で x が並んでたとしても
それらを消し切るのには少なくとも (n+1)/2 回かかる。
note1 2 3 4 5 6
x x x x x x
note9
1 2 4 9 5 8 7 3 6
1 2 3 4 5 6 7 8 9
x x x x
1 2 4 9 5 8 3 7 6
1 2 3 4 5 6 7 8 9
x x x
1 2 4 9 5 8 3 7 6
1 2 3 4 5 6 7 8 9
x x x
1 2 4 9 8 5 3 7 6
1 2 3 4 5 6 7 8 9
x x
2 1 4 9 8 5 3 7 6
2 1 3 4 5 6 7 8 9
一気に二つ x も消える場合がある。
アルゴリズム
minimum_count = 0
前から p を一度読み取る（ループ変数 i ）
combo = 0 と定義する。
もし i + 1 == A[i] であれば
combo += 1
そうでなければ
minimum_count += (combo + 1) / 2
combo = 0
（切り上げ）
minimum_count を出力する。
bugfix 端処理
最後まで x が引き続いたときに答えに加算されていない。
なぜ気づけなかったのか
全ての x の連続した区間に対して、"右端"が存在すると思い込んでいたため
if 文がどの範囲で実行されるかについて検証が必要だった。
擬似的な実行例
cpp9
1 2 4 9 5 8 7 3 6
^ ^ ^ ^
combo = 2 -> 3 / 2 = 1: min_count = 1
combo = 1 -> 2 / 2 = 1: min_count = 2
combo = 1 -> 2 / 2 = 1: min_count = 2
問題例を手で実行し通すべきだったかも...。