AtCoder Regular Contest 159 C - Permutation Addition
メモ
不変量について考えたい。
こういう時（何かを足していってそれぞれの値を合わせる時とか）は
全体の合計に注目するといいことが多い気がする。
どういう操作をしても不変なものを考えると
どう足しても一回で増える和は同じである
全体の合計はNの倍数になる必要がある。
N2 = (N(N+1))/2として
k回足すと合計が以下のようになり
sigma(A) + N2 * K = 0(mod N)
mod Nで0になる必要がある
ここでN2 * 2 = 0(mod N)なので
sigma(A)=0 (mod N)か sigma(A) + N2 = 0(mod N)が成り立つ必要がある
これが成り立つ場合必ずできる。
一回Aの合計がNの倍数になるように順列を高々一回足してやる
このNの倍数という良い性質を満たしたまま操作をしていきたいため、順列を毎回二回ずつ足すことを考える。
結論から言うと
1, 2, 3, 4, 5, 6, 7
7, 6, 5, 4, 3, 2, 1
と足すと全体の差分に0が足されるので
上手くswapしてやると
1, 2, 3, 4, 5, 6, 7
6, 7, 5, 4, 3, 2, 1
などで
-1, +1,+0+0+0+0
のようにできる
この問題の操作はこの+1, -1だけを足す操作に言い換えても答えが変わらない。
現状の合計はNで割り切れることが確定しており、一回の操作で合計が変わらないため
+1, -1を繰り返すことですべての値を同じに出来る
類題
0,1,2を足して同じ数を作る問題を
-1, 0, -1を足す問題と言い換え、合計を不変にする操作が同じ
