Codeforces #421 (Div. 1) B: Mister B and PR Shifts
まず初期状態のdeviationを計算しておく。
1回のcyclic shiftでdeviationの値がどのように変化するかを知りたい。
基本的には
p[i] < iのときp[i]の位置はiに近づくので、そのような値はdeviationを1だけ減らす。
p[i]>=iのときp[i]の位置はiから離れるので、そのような値はdeviationを1だけ増やす。
なので、次のcyclic shiftによってdeviationを減らす値と増やす値を数えておく。仮にそれぞれx, yとする。それによって毎ターンdeviationを増減させる。
ただし、この方針では右端が例外になる。
i(i>1)番目にある値はn-i回目のシフトで右端から左端へ移動する。このときだけ、deviationの計算をうまく分ける。
すなわち値zについて考える場合
deviationから|n-z|を引いて|1-z|を足す。また、このときx, yが変わる場合があるので注意。上図では
3は3から離れる => 3は3に近づく
というふうに状態が変化している。すなわち、
x++, y--
となる。
x, yの変化はもう1種類あって
のようにp[i]=iになるような場合で
x--, y++となる。
ただし、
のような場合に注意。
コード
Submission #28107263 - Codeforces