競技プログラミング The Boss Rush!!! : A - Revenge of Voronoi - ボロノイの逆襲

これは本番は出てないけど、練習を兼ねて実装。
自分では回答を考え付かないので、回答を見ながら実装。
http://yuha-c83.contest.atcoder.jp/tasks/yuha_c83_01

ボロノイ図が与えられて、元の中心点を求める問題。
回答を見ながらやると、以下のようになる。

• 境界が隣接する２色を選び、その間で矛盾が起きないようその２色の中心点候補を選ぶ
• 中心点候補から、26色全部で矛盾が起きないような組み合わせを探索していく

最初さらっと組んだら、コード自体は動いたけど大サイズでTLE出まくってびっくり。
頑張ってガリガリ探索範囲を狭めて何とかクリア。
これ、元ネタはW,H<=32なのね…。

int W,H;
set<pair<int, int> > mine[26];
vector<pair<int, int> > minenei[26][26];

int canmask[51][51];
ll tok[51][51][51];
int neimask[26];
vector<int> nei[26];

vector<int> mlist;
int revid[26];

char str[100][100];
int npat,newest,mask;

pair<int,int> dfsc[26];

void enum_pcan(int f,int t) {
	set<pair<int, int> >::iterator fit,tit;
	vector<pair<int, int> >::iterator it2;
	
	for(fit=mine[f].begin();fit!=mine[f].end();fit++) for(tit=mine[t].begin();tit!=mine[t].end();tit++) {
		bool ok=true;
		
		// 境界のマスだけチェック
		for(it2=minenei[f][t].begin();ok&&it2!=minenei[f][t].end();it2++) {
			int fd = abs(fit->first-it2->first)+abs(fit->second-it2->second);
			int td = abs(tit->first-it2->first)+abs(tit->second-it2->second);
			if(td<fd) ok=false;
		}
		for(it2=minenei[t][f].begin();ok&&it2!=minenei[t][f].end();it2++) {
			int fd = abs(fit->first-it2->first)+abs(fit->second-it2->second);
			int td = abs(tit->first-it2->first)+abs(tit->second-it2->second);
			if(fd<=td) ok=false;
		}
		
		if(ok){
			tok[fit->first][fit->second][tit->first] |= 1LL<<tit->second;
			tok[tit->first][tit->second][fit->first] |= 1LL<<fit->second;
			canmask[fit->first][fit->second]|=1<<t;
			canmask[tit->first][tit->second]|=1<<f;
		}
	}
}

void output() {
	int x;
	FOR(x,26) if(!mine[x].empty()) {
		_P("%c %d %d\n",x+'a',dfsc[x].first,dfsc[x].second);
	}
}

void dfs(int id, vector<pair<int,int> > *pc) {
	vector<pair<int,int> > npc[26];
	int x,y,cur;
	
	if(id==mlist.size()) {
		output();
		exit(0);
	}
	
	cur = mlist[id];
	FOR(x,26) if(!(neimask[cur] & (1<<x))) npc[x] = pc[x];

	for(vector<pair<int, int> >::iterator fit=pc[cur].begin();fit!=pc[cur].end();fit++) {
		bool ok=true;
		FOR(x,26) {
			if(revid[x] < id || !(neimask[cur] & (1<<x))) continue;
			
			npc[x].clear();
			FOR(y,pc[x].size()) {
				if(tok[fit->first][fit->second][pc[x][y].first] & (1LL<<pc[x][y].second)) {
					npc[x].push_back(pc[x][y]);
				}
			}
			if(npc[x].empty()) {
				ok=false;
				break;
			}
		}
		if(ok) {
			dfsc[cur]=*fit;
			dfs(id+1,npc);
		}
	}
	return;
	
}

void dfs_c(int cur, int& mask) {
	int x;
	
	mask |= 1<<cur;
	revid[cur]=mlist.size();
	mlist.push_back(cur);
	FOR(x,26) {
		if(!(mask & (1<<cur)) && (neimask[cur] & (1<<x))) dfs_c(x,mask);
	}
}

void solve() {
	int x,y,i,j,res,TM,nc;
	
	W=GETi();
	H=GETi();
	FOR(y,H) {
		GETs(str[y]);
		FOR(x,W) {
			int c=str[y][x]-'a';
			if(mine[c].empty()){ npat++; newest=c;}
			mine[c].insert(make_pair(x,y));
		}
	}
	
	FOR(y,H) FOR(x,W) {
		if(x<W-1 && str[y][x]!=str[y][x+1]) {
			minenei[str[y][x]-'a'][str[y][x+1]-'a'].push_back(make_pair(x,y));
			neimask[str[y][x]-'a'] |= 1<<(str[y][x+1]-'a');
			minenei[str[y][x+1]-'a'][str[y][x]-'a'].push_back(make_pair(x+1,y));
			neimask[str[y][x+1]-'a'] |= 1<<(str[y][x]-'a');
		}
		if(y<H-1 && str[y][x]!=str[y+1][x]){
			minenei[str[y][x]-'a'][str[y+1][x]-'a'].push_back(make_pair(x,y));
			neimask[str[y][x]-'a'] |= 1<<(str[y+1][x]-'a');
			minenei[str[y+1][x]-'a'][str[y][x]-'a'].push_back(make_pair(x,y+1));
			neimask[str[y+1][x]-'a'] |= 1<<(str[y][x]-'a');
		}
	}
	
	// 1種類なら終わる
	if(npat==1) {
		_P("%c %d %d\n",newest+'a',0,0);
		return;
	}
	
	FOR(x,26) FOR(y,26) if(x<y && (neimask[x] & (1<<y))) enum_pcan(x,y);
	//候補を絞る
	int mask=0;
	vector<pair<int, int> > pcan[26];
	
	FOR(x,26) {
		revid[x]=-1;
		if(mine[x].empty()) mask |= 1<<x;
		for(set<pair<int, int> >::iterator fit=mine[x].begin();fit!=mine[x].end();fit++) {
			if(canmask[fit->first][fit->second] == neimask[x]) pcan[x].push_back(*fit);
		}
		FOR(y,26) if(neimask[x] & (1<<y)) nei[x].push_back(y);
	}
	
	FOR(x,26) if((mask & (1<<x))==0) dfs_c(x,mask);
	dfs(0, pcan);
	
	return;
}

まとめ

面白い問題。
アルゴリズムとしては正しい方向性で書けたのに、TLEがなかなか解けないので苦労した。
余分な探索を減らすようなコードを書かないとな…。