考察
中央をまたぐ加算区間は、左右を折り返して相殺すると中央をまたがない一つの区間へ置き換えられる。m=⌊N/2⌋、B_i=A_i−A_{N+1−i} mod Mとすれば、Bの区間へ+1または−1を加え全0にする問題になる。右側の操作がBへの−1も実現する。
B_0=B_{m+1}=0、C_i=B_i−B_{i−1} mod M (1≤i≤m+1)を0..M−1で持つ。Bの区間操作はCの二点間の一unit移送である。任意の二点を増加・減少のどちら向きにも選べるので、ΣC_iを保存しながらCを全0 mod Mへする最小移送数を求めればよい。
ΣC_i=tMとする。整数としての最終値は各座標のMの倍数で総和tM。移送総数は、増やす量と減らす量が等しい時の片方の和である。最適な最終値は各座標0またはMとしてよい:負のM倍数や2M以上へ送ると、その座標と逆方向の変更をしている座標の間でMを移し、費用を増やさず0..Mへ近づけられる。従って最終値Mへする座標をちょうどt個選び、残りk=m+1−t個を0へ減らす。
0へ減らす集合Yの減少総数はΣ_{i∈Y}C_i、補集合をMへ増やす総数はΣ_{i∉Y}(M−C_i)。|Y|=m+1−tで両者は等しく、任意の移送をpairingできるのでその和が操作数になる。Yへ入れるべきなのは小さいC_iのk個。ここでYは減少側であり、増加側と取り違えない。0のCは費用0でYへ入る。
Cを昇順sortし、最初のk個の和を返す。N=1やM=1では全Cが0で答え0。例えばC=(1,1,3),M=5ではt=1,k=2、小さい二つから各1を減らし、最後を3から5へ2増やす二回の移送で終わる。
典型の発動条件
区間±1を両端の差分移送へ変換する。法Mの0へ戻すときは整数の持上げを0/Mへ選び、総量保存から選ぶ個数を先に定める。増加費用M−Cと減少費用Cを区別して交換論を使う。
問題固有の要素
palindrome 条件は対称pair差へ落とし、range operation はさらに差分の二点 operationへ落とすと一次元輸送問題になる。
別の問題へ持ち帰る視点: subsetが個数と総和だけで評価されるなら、個数固定後はsort prefixが最適になる。
正当性
中央をまたぐ操作の正規化で、Bへの区間±1と元の操作が同じ費用で対応する。差分Cでは区間操作が任意の二点間の一unit移送となる。Cを0 mod Mへ送る最終整数値は総和tMを持つM倍数で、負や2M以上の座標はM単位の交換で費用を増やさず0またはMへ近づけられる。最終値Mの座標はt個、0の座標はk=m+1−t個だから、減少側Yの総量と増加側の総量が等しく、全量をpairingして実現できる。固定個数kの減少側の和は小さいCのk個を選ぶ時に最小となるため、そのprefix和が最小操作数である。
実装上の注意
- mod差を常に0..M-1へ正規化し、B末尾の0番兵から生じる最後のCを忘れない。kが差分列の全長になる境界も許す。
復習の核
- 一回の左側区間操作が B と C をどう変えるかを追い、減少側集合サイズkの導出を操作回数二式から再現する。
計算量と制約
時間
O(N log N)、差分列のsortを含む。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\le T; 1\le N\le 2\times 10^5; 1\le M\le 10^9; 0\le A_i < M; The sum of N over all test cases is at most 2\times 10^5.; All input values are integers.
出典