Codeforces #960 : Div2 D. Grid Puzzle

今年最後です。
https://codeforces.com/contest/1990/problem/D

問題

N*Nのグリッドがある。
各行iは、左からA[i]列目までのセルが黒く塗られており、それより右側は白く塗られている。

以下の処理を行い、全セルを白くするには最小何回処理を行えばよいか。

• 2*2の領域を白くする
• 指定した1行全部を白くする

解法

2*2の領域を白くするとき、あり得るのは左端から2列分を白くするか、3～4列目を白くする場合である。
5列目以上まで黒いなら、行全体を白くした方が良い。

よって1行目からどん欲に見て、直前の表で2*2で白くするパターンの有無を踏まえて、次の行でどのパターンで消すと処理回数が最小になるか判断していく。

int T,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int f=0,s=0;
		int ret=0;
		FOR(i,N) {
			cin>>x;
			if(f==0&&s==0) {
				//2個以下なら2*2、それ以上なら行消し
				if(x) {
					ret++;
					if(x<=2) f=1;
				}
			}
			else if(f) {
				f=0;
				if(x>=3) {
					ret++;
					if(x<=4) s=1;
				}
			}
			else {
				s=0;
				if(x) {
					ret++;
					if(x<=4) f=1;
				}
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

来年もよろしくお願いします。