yukicoder : No.1584 Stones around Circle Pond

こういう言い換え苦手。
https://yukicoder.me/problems/no/1584

問題

長さ2Lの円周状の池があり、その周囲に2N個のスポットがある。
なお、各スポットの反対側距離Lのところに、もう一つのスポットがあることが確定している。

今数列Bを初期値0の数列とする。
今1つスポットを選択すると、全スポットiに対し、選択したスポットからの最短距離と同じ数だけ数列B[i]に加算する。
最終的にBを指定された値と一致させられるか判定せよ。

解法

E[i]を、各スポットの選択回数とする。
B[i]とB[i+1]を比べると、iに近い側とi+1に近い側どちらが選ばれるかで、両スポットの距離分だけ差がつくので、そこからどちら側が何回余分に選ばれたかがわかる。

この値を、1つずらしたスポット同士見比べることで、E[i]とE[i+N]の差が確定する。
そこで、E[i]とE[i+N]で多くなければいけない方について、それだけ実際に選んでみよう。

あとは、あるスポットとその対岸を1回ずつ選ぶと、B[i]を全体的にLだけ増加できるので、例えばB[0]が指定値に一致するまでLずつ増加させてみよう。

int N,L;
int D[302];
ll B[202];

ll F[202],G[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) cin>>D[i];
	for(i=N-1;i>=0;i--) {
		D[i+N]=D[i]+L;
		D[i+2*N]=D[i+N]+L;
	}
	FOR(i,2*N) cin>>B[i];
	
	
	FOR(i,2*N) {
		ll BS=B[(i+1)%(2*N)]-B[i];
		ll DS=D[(i+1)]-D[i];
		
		
		if(BS%DS) {
			cout<<"No"<<endl;
			return;
		}
		F[i]=BS/DS;
	}
	
	FOR(i,2*N) {
		G[i]=F[i]-F[(i+2*N-1)%(2*N)];
		if(G[i]%2) {
			cout<<"No"<<endl;
			return;
		}
		G[i]/=2;
		if(i>=N&&G[i]!=-G[i-N]) {
			cout<<"No"<<endl;
			return;
		}
	}
	FOR(i,2*N) if(G[i]>0) {
		FOR(x,2*N) {
			ll d=min(abs(D[i]-D[x]),2*L-abs(D[i]-D[x]));
			B[x]-=d*G[i];
		}
	}
	if(B[0]<0||B[0]%L) {
		cout<<"No"<<endl;
		return;
	}
	FOR(i,2*N) if(B[i]!=B[0]) {
		cout<<"No"<<endl;
		return;
	}
	cout<<"Yes"<<endl;
	
}

まとめ

1つずれたものを考える、以前ARC-Fでも出たけどさっと思いつかないんだよな。