Codeforces #754 Div2 : E. Array Equalizer

これはどうにか本番解けた。
https://codeforces.com/contest/1605/problem/E

問題

2つの整数列A,Bが与えられる。
Aに対し、整数iを指定し、A[k*i]に対応する値を、すべてインクリメントするかすべてデクリメントすることができる。
この処理を用いて、AをBに一致させる最小回数を求めたい。

B[1]が複数指定される。
それぞれの場合における、上記処理の最小処理回数を求めよ。

解法

まず、最小回数はiの小さい順に選び、A[i]をB[i]に一致させていく一択である。
B[1]が1～100000を取るとき、A[i]をB[i]に合わせるためにA[k*i]がどうなるかをB[1]の関数で表現していく。

int N;
int A[202020],B[202020];
int D[202020],D2[202020];
vector<int> C[2];

ll RS[1010101];
ll LS[1010101];
ll sum[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	for(i=2;i<=N;i++) A[i]=1;
	for(i=2;i<=N;i++) B[i]=0;
	
	for(i=2;i<=N;i++) {
		D[i]=B[i]-A[i];
		for(j=i;j<=N;j+=i) A[j]+=D[i];
	}
	
	FOR(i,N) cin>>A[i+1];
	FOR(i,N) cin>>B[i+1];
	
	B[1]=A[1];
	ll base=0;
	for(i=2;i<=N;i++) {
		D2[i]=B[i]-A[i];
		for(j=i;j<=N;j+=i) A[j]+=D2[i];
		
		if(D[i]==0) {
			base+=abs(D2[i]);
		}
		else {
			x=A[1]-D[i]*D2[i];
			
			if(x<0) {
				base+=-x-1;
				RS[0]++;
			}
			else if(x>1000000) {
				base+=x-1000000-1;
				LS[1000000]++;
			}
			else {
				RS[x+1]++;
				LS[x-1]++;
			}
		}
	}
	ll a=base;
	int cur=0;
	for(i=0;i<=1000000;i++) {
		cur+=RS[i];
		a+=cur;
		sum[i]+=a;
	}
	a=cur=0;
	for(i=1000000;i>=0;i--) {
		cur+=LS[i];
		a+=cur;
		sum[i]+=a;
	}
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>x;
		cout<<sum[x]+abs(x-A[1])<<endl;
	}
	
	
}

まとめ

本番も割とてこずってるな…。