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だけ増やす。

f:id:parukii:20170628125215j:plain

なので、次のcyclic shiftによってdeviationを減らす値と増やす値を数えておく。仮にそれぞれx, yとする。それによって毎ターンdeviationを増減させる。

ただし、この方針では右端が例外になる。

f:id:parukii:20170628130012j:plain

i(i>1)番目にある値はn-i回目のシフトで右端から左端へ移動する。このときだけ、deviationの計算をうまく分ける。

すなわち値zについて考える場合

deviationから|n-z|を引いて|1-z|を足す。また、このときx, yが変わる場合があるので注意。上図では

3は3から離れる => 3は3に近づく

というふうに状態が変化している。すなわち、

x++, y--

となる。

x, yの変化はもう1種類あって

f:id:parukii:20170628130807j:plain

のようにp[i]=iになるような場合で

x--, y++となる。

ただし、

f:id:parukii:20170628131331j:plain

のような場合に注意。

コード

Submission #28107263 - Codeforces