TSG LIVE! 4 プログラミングコンテスト : G : Emoji ha eemoji

これは言われてみりゃそりゃそうだという問題。
https://www.hackerrank.com/contests/tsg-live-4-programming-contest/challenges/tsg-live-4-procon-emoji-ha-eemoji

問題

1辺の長さがN(2のべき乗)のグリッドが与えられる。
各セルは白か黒に塗られているが、一部Kマス(最大10)では色が未定である。

このグリッドのスコアを以下のように定義する。
pを1～Nの各2のべき乗において、グリッドをp*pの矩形に分けたケースを考え、その際各矩形の塗り方のユニークなものの数をスコアとする。
ただし、pが異なる矩形であっても、相似の関係にあるものは同一とみなす。

未定のマスの色を白黒任意に設定できるとき、グリッドのスコアを最小化せよ。

解法

未定マスを除き、全マス白または全マス黒なら、未定マスも含め全マス1色で塗ってスコアが1になる。
以下、白黒それぞれ最低1マスずつは存在するものとする。

まず未定のマスがないときのスコアを考える。
pの小さい順に矩形を順に見ていき、塗り方に応じたIDを振ることを考える。
まず、全体が白・全体が黒のケースは先にIDとして1・2を設定しておく。
以後、p=2から順に見ていく。

対象の矩形を、上下左右で2分割ずつして4つに分け、それぞれのIDを考える。
その4つのIDの組が過去に登場済みなら、その矩形は過去のものと同じIDを振り、新規なら新たなIDを振ろう。
最終的なスコアはIDの最大値となる。

次に未定マスがある場合を考える。
まず、全矩形のパターンのうち未定マスを含まないものについて、前述のIDを求めよう。
そのような矩形は高々KlogN個しかない。
未定マスの色の塗り分け2^K通りを総当たりし、これら未定マスを含む矩形についてIDを考えてみればよい。

int N;
int L;
string S[1024];
int pat[11][1024][1024];
map<vector<int>,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(1<<(L+1)<=N) L++;
	int cnt[2]={};
	vector<pair<int,int>> cand;
	FOR(y,N) {
		cin>>S[y];
		cnt[0]+=count(ALL(S[y]),'#');
		cnt[1]+=count(ALL(S[y]),'.');
		FOR(x,N) if(S[y][x]=='?') cand.push_back({y,x});
	}
	if(cnt[0]==0 || cnt[1]==0) return _P("1\n");
	M[{1,1,1,1}]=1;
	M[{2,2,2,2}]=2;
	FOR(y,N) FOR(x,N) {
		if(S[y][x]=='#') pat[0][y][x]=1;
		else if(S[y][x]=='.') pat[0][y][x]=2;
	}
	
	vector<vector<int>> unfixed;
	for(i=1;i<=L;i++) {
		int step=(1<<i);
		for(y=0;y<N;y+=step) for(x=0;x<N;x+=step) {
			vector<int> V;
			V.push_back(pat[i-1][y][x]);
			V.push_back(pat[i-1][y+step/2][x]);
			V.push_back(pat[i-1][y][x+step/2]);
			V.push_back(pat[i-1][y+step/2][x+step/2]);
			if(count(ALL(V),0)) {
				unfixed.push_back({i,y,x});
			}
			else if(M.count(V)) {
				pat[i][y][x]=M[V];
			}
			else {
				pat[i][y][x]=M.size()+1;
				M[V]=pat[i][y][x];
			}
		}
	}
	
	int mi=1<<30;
	for(int mask=0;mask<1<<cand.size();mask++) {
		FOR(i,cand.size()) {
			pat[0][cand[i].first][cand[i].second]=1+((mask>>i)&1);
		}
		vector<vector<int>> added;
		FORR(u,unfixed) {
			i=u[0];
			y=u[1];
			x=u[2];
			vector<int> V;
			int step=(1<<i);
			V.push_back(pat[i-1][y][x]);
			V.push_back(pat[i-1][y+step/2][x]);
			V.push_back(pat[i-1][y][x+step/2]);
			V.push_back(pat[i-1][y+step/2][x+step/2]);
			if(M.count(V)) {
				pat[i][y][x]=M[V];
			}
			else {
				pat[i][y][x]=M.size()+1;
				M[V]=pat[i][y][x];
				added.push_back(V);
			}
		}
		mi=min(mi,(int)M.size());
		FORR(a,added) M.erase(a);
		
	}
	cout<<mi<<endl;
}

まとめ

わかってしまえばさっくりなんだけどね。