Codeforces ECR #136 : E. Cleaning Robot

本番割と苦戦。
https://codeforces.com/contest/1739/problem/E

問題

2*Nのグリッドが与えられる。
一部セルは汚れている。

左上マスに自動清掃マシンを置くことを考える。
このマシンは、マンハッタン距離で最寄りの汚れたセルに移動し、そのセルを綺麗にするということを繰り返す。
ただし、途中複数の汚れたマスが等距離にある事態が発生してはならない。

最初、この事態を防ぐためにいくつかのマスを綺麗にしておくことができる。
最大で、何マス汚れたマスを放置できるか。

解法

マシンが右から左に動くことはない。
よって左から順にDPで求めて行く。
状態としては、マシンが上下どちらのセルにいるかと、上下のマスの汚れたマスを残しているかどうか、8通りを状態として持ちながら、次に上下どちらの行の汚れたマスに移動するか計算していこう。

int N;
string S[2];
int R[2][202020];
int dp[2][2][2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>S[0]>>S[1];
	N+=2;
	S[0]+="00";
	S[1]+="00";
	
	R[0][N]=R[1][N]=N+2;
	R[0][N+1]=R[1][N+1]=N+2;
	int total=0;
	for(i=N-1;i>=0;i--) {
		FOR(j,2) {
			R[j][i]=R[j][i+1];
			if(S[j][i]=='1') {
				R[j][i]=i;
				total++;
			}
		}
	}
	FOR(i,N) FOR(x,2) FOR(y,2) FOR(k,2) dp[x][y][k][i]=1<<30;
	dp[0][0][0][0]=0;
	int ret=1<<30;
	FOR(x,N) {
		FOR(i,2) FOR(k,2) FOR(y,2) {
			int sx=R[y][x+1];
			int sx2=R[y^1][x+i];
			if(k) sx2=R[y^1][x+2];
			int cur=dp[y][i][k][x];
			if(cur>=1<<29) continue;
				
			if(sx>N&&sx2>N) {
				ret=min(ret,cur);
			}
			else {
				if(sx<=sx2) {
					chmin(dp[y][(sx==x+1)&&k][0][sx],cur);
				}
				else if(sx2+1==sx) {
					// same line
					chmin(dp[y][(sx==x+1)&&k][0][sx],cur+1);
					// other line
					chmin(dp[y^1][sx2==x][1][sx2],cur+1);
				}
				else {
					chmin(dp[y^1][sx2==x][0][sx2],cur);
					chmin(dp[y][1][0][sx2],cur+1);
				}
			}
		}
	}
	cout<<total-ret<<endl;
	
}

まとめ

細かいところを詰めていくのにだいぶ手間取った。