Codeforces #766 : Div2 F. Not Splitting

本番中に解き切れず。
https://codeforces.com/contest/1627/problem/F

問題

K*Kのグリッドがある。
これをセルに沿って切れ目を入れ、平行移動・回転・反転して重なる2つのセル群に分割したい。
ただし条件として、間に切れ目を入れたくない２セルの対が多数与えられる。

極力、間に切れ目を入れないセル対の条件を満たして分割したい。最大何個条件を満たせるか。

解法

平行移動・回転・反転とあるが、実質グリッドの中心を180度点対称に分けることを考えればよい。

グリッドの中心から、セルの間の線をたどってグリッドの周辺部に移動することを考える。
この線を点対称に180度回転させれば条件を満たす分け方となる。

そこで、まずセル対に対し、180度回転させた位置の2セルに対しても同じ条件があるものとみなす。
そのうえで、「グリッドの中心から、セルの間の線をたどってグリッドの周辺部に移動する」際、違反する条件数を最小化すればよいので、ダイクストラ法で解くことができる。

int T;
int N,K;
int V[1010][1010];
int H[1010][1010];
int dp[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(y,K+2) FOR(x,K+2) {
			H[y][x]=V[y][x]=0;
			dp[y][x]=1<<25;
		}
		FOR(i,N) {
			int y1,x1,y2,x2;
			cin>>y1>>x1>>y2>>x2;
			if(y1==y2) V[y1][min(x1,x2)]++;
			else H[min(y1,y2)][x1]++;
			y1=K+1-y1;
			y2=K+1-y2;
			x1=K+1-x1;
			x2=K+1-x2;
			if(y1==y2) V[y1][min(x1,x2)]++;
			else H[min(y1,y2)][x1]++;
		}
		
		dp[K/2+1][K/2+1]=0;
		priority_queue<pair<int,int>> Q;
		Q.push({0,(K/2+1)*1000+(K/2+1)});
		while(Q.size()) {
			int co=-Q.top().first;
			int ty=Q.top().second/1000;
			int tx=Q.top().second%1000;
			Q.pop();
			if(dp[ty][tx]!=co) continue;
			
			if(ty>1&&dp[ty-1][tx]>co+V[ty-1][tx-1]) {
				dp[ty-1][tx]=co+V[ty-1][tx-1];
				Q.push({-dp[ty-1][tx],(ty-1)*1000+tx});
			}
			if(ty+1<=K+1&&dp[ty+1][tx]>co+V[ty][tx-1]) {
				dp[ty+1][tx]=co+V[ty][tx-1];
				Q.push({-dp[ty+1][tx],(ty+1)*1000+tx});
			}
			if(tx>1&&dp[ty][tx-1]>co+H[ty-1][tx-1]) {
				dp[ty][tx-1]=co+H[ty-1][tx-1];
				Q.push({-dp[ty][tx-1],(ty)*1000+tx-1});
			}
			if(tx+1<=K+1&&dp[ty][tx+1]>co+H[ty-1][tx]) {
				dp[ty][tx+1]=co+H[ty-1][tx];
				Q.push({-dp[ty][tx+1],(ty)*1000+tx+1});
			}
			
			
		}
		
		cout<<N-dp[1][1]<<endl;
	}
}

まとめ

気付いてしまえば簡単。