AtCoder ABC #159 : E - Dividing Chocolate

今日は割と簡単目だったみたいね。
https://atcoder.jp/contests/abc159/tasks/abc159_e

問題

H*Wの白黒グリッドが与えられる。
マス目に沿った直線でグリッドを分割し(分割は常に端から端まで行われる)、各分割領域の白マスをK個以下にしたい。
最小分割数を求めよ。

解法

Hが小さいので横方向の切れ目は2^(H-1)通り総当たりし、あとは端から順にK個を超えそうな段階で縦の切れ目を

int H,W,K;
string S[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) cin>>S[y];
	int mi=1<<30;
	
	int mask;
	FOR(mask,(1<<(H-1))) {
		int to[10]={};
		int tar=0;
		FOR(i,H) {
			to[i]=tar;
			if(mask&(1<<i)) tar++;
		}
		tar++;
		int ret=__builtin_popcount(mask);
		int cnt[10]={};
		FOR(x,W) {
			FOR(y,H) {
				if(S[y][x]=='1') cnt[to[y]]++;
			}
			int ng=0;
			FOR(i,tar) if(cnt[i]>K) {
				ret++;
				FOR(y,tar) cnt[y]=0;
				FOR(y,H) if(S[y][x]=='1') cnt[to[y]]++;
				break;
			}
			FOR(i,tar) if(cnt[i]>K) ret=1LL<<30;
		}
		mi=min(mi,ret);
		
	}
	cout<<mi<<endl;
	
}

まとめ

旧ABCだとDに来るか来ないかぐらいの難易度？