似たような問題昔SRMで見たような。
https://yukicoder.me/problems/no/2603
問題
N要素の整数列A,Bが与えられる。
Aの連続する要素を指定して、全体を任意の整数x加算または減算し、Mで割った余りに置き換えることができる。
この処理を何度か使ってAをBにしたい。最小でxの絶対値の総和はいくつか。
解法
まず最初にAとBの差を取っておく。この数列をCとする。
Cの階差数列をDと置く。
1回の処理では、Dの1要素をx加算し、1要素を1減算することができるとして、Dの各要素をMの倍数にすることを考えよう。
Dの非0の値のうち、最小値と最大値を取り出し、前者が0または後者がMになるまで、前者を1減算、後者を1加算していくことを繰り返せばよい。
int N,M; int A[202020],B[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>A[i+1]; FOR(i,N) { cin>>x; A[i+1]=x-A[i+1]; if(A[i+1]<0) A[i+1]+=M; } deque<int> Q; for(i=1;i<=N+1;i++) { x=(A[i]-A[i-1]+M)%M; Q.push_back(x); } sort(ALL(Q)); ll ret=0; while(Q.size()) { while(Q.size()&&Q.front()==0) Q.pop_front(); while(Q.size()&&Q.back()==M) Q.pop_back(); if(Q.empty()) break; assert(Q.size()>1); x=min(Q.front(),M-Q.back()); ret+=x; Q.front()-=x; Q.back()+=x; } cout<<ret<<endl; }
まとめ
SRMの問題は自転車の番号式ロックみたいな題材だったかな。