yukicoder : No.861 ケーキカット

割とゴリ押しがきく。
https://yukicoder.me/problems/no/861

問題

5*5の盤面があり、各マスに数値が書かれている。
これらのマスを２色に塗り分けることを考える。
その際、同色のマスはすべて連結していなければならない。

両色のマスに書かれた数値の総和の差の最小値を求めよ。

解法

左上のマスの色を固定すると、連結条件を除いて塗り分け方は2^24通りある。
ただ、これで2^24回連結判定しようとするとTLEする。
なので、もう少し工夫して全探索しよう。

以下では、左上と同じ色のマスをDFSの要領で隣接マスを取り込んで拡大しながら総当たりしている。
この時点で、片方の色が連結であることは常時保障されるので、2^24通りのうち通る状態がだいぶ絞られる。

ll C[5][5];
ll S;

int vis[1<<25];
ll ret=1LL<<60;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int gmask(int mask,int y,int x) {
	return (mask>>(y*5+x))&1;
}

void dfs(int mask,ll s) {
	if(vis[mask]) return;
	vis[mask]=1;
	int y,x;
	
	if(abs(s-(S-s))<ret) {
		UF<25> uf;
		FOR(y,5) FOR(x,5) {
			if(x&&gmask(mask,y,x)==gmask(mask,y,x-1)) uf(y*5+x-1,y*5+x);
			if(y&&gmask(mask,y,x)==gmask(mask,y-1,x)) uf(y*5+x-5,y*5+x);
		}
		int num=0;
		FOR(x,25) if(uf[x]==x) num++;
		if(num<=2) ret=abs(s-(S-s));
	}
	
	FOR(y,5) FOR(x,5) if(gmask(mask,y,x)==0) {
		int ok=0;
		if(y) ok|=gmask(mask,y-1,x);
		if(y<4) ok|=gmask(mask,y+1,x);
		if(x) ok|=gmask(mask,y,x-1);
		if(x<4) ok|=gmask(mask,y,x+1);
		if(ok) dfs(mask | (1<<(y*5+x)),s+C[y][x]);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(y,5) FOR(x,5) {
		cin>>C[y][x];
		S+=C[y][x];
	}
	
	
	dfs(1,C[0][0]);
	cout<<ret<<endl;
}

まとめ

方針が立った後もちょっと面倒な問題。