Codeforces #996 : Div2 F. Cosmic Divide

シンプルな問題設定。
https://codeforces.com/contest/2055/problem/F

問題

凸なポリオミノが与えられる。
これを2つの連結で合同なポリオミノに分割できるか判定せよ。

解法

コーナーケースとして横に2分割できるケースは先に処理する。
そうでない場合、最上段を1つ目のポリオミノで占有するとし、2つ目のポリオミノが何段目から開始するか総当たりする。
また、2つ目のポリオミノが1つ目に対し左右どちらに来るかも総当たりする。

これらが決まると、2つのポリオミノのオフセットが定まるので、両者を合同にできるか判定できる。

int T,N;
int L[202020],R[202020];
int TL[202020],TR[202020];
ll A[402020];

int ok(int dy) {
	int i,y;
	
	ll cur=0;
	for(i=0;i<=N;i+=dy) {
		if(cur>A[i+dy]-A[i]) return 0;
		cur=A[i+dy]-A[i]-cur;
	}
	if(cur) return 0;
	
	FOR(i,N) TL[i]=L[i],TR[i]=R[i];
	int dx=TL[dy]-TL[0];
	
	int preL=-1,preR=-1;
	for(y=0;y+dy<N;y++) {
		if(y) {
			if(TL[y]>=preR) return 0;
			if(TR[y]<=preL) return 0;
		}
		
		if(TR[y]-TL[y]<=0) return 0;
		if(TR[y]-TL[y]>TR[y+dy]-TL[y+dy]) return 0;
		if(TL[y]+dx==TL[y+dy]) {
			TL[y+dy]+=TR[y]-TL[y];
		}
		else if(TR[y]+dx==TR[y+dy]) {
			TR[y+dy]-=TR[y]-TL[y];
		}
		else {
			return 0;
		}
		preR=TR[y];
		preL=TL[y];
	}
	for(y=N-dy;y<N;y++) if(TR[y]!=TL[y]) return 0;
	return 1;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(r,T) {
		cin>>N;
		FOR(i,N) {
			cin>>L[i]>>R[i];
			L[i]--;
		}
		
		
		//横に分割
		if((R[0]-L[0])%2==0) {
			FOR(y,N-1) {
				if(R[y+1]-L[y+1]!=R[0]-L[0]) break;
				if(abs(R[y]-R[y+1])>=(R[0]-L[0])/2) break;
			}
			if(y==N-1) {
				cout<<"YES"<<endl;
				continue;
			}
		}

		FOR(k,2) {
			
			FOR(i,N) A[i+1]=A[i]+R[i]-L[i];
			FOR(i,N) A[N+i+1]=A[N+i];
			for(i=1;i<=N/2;i++) if(ok(i)) break;
			if(i<=N/2) break;
			
			
			reverse(L,L+N);
			reverse(R,R+N);
			
		}
		
		if(k==2) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
}

まとめ

Eより簡単かも…？