kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2015 Round2B Medium Balance

SRM

問題文がややこしいなぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=13841

問題

無限に広がる２次元グリッドがある。
各セルは白か黒の何れかである。

ここで、グリッドの一部の形状が文字列配列initialで与えられる。
initial[y][x]は、(y*10000, x*10000)-(y*10000+9999, x*10000+9999)の領域のセルが白黒どちらかであるかを表したものである。
initialに含まれない領域はすべて白であるとしてよい。

このグリッドにおいて、同色の隣接セルで連結されたセル群をcomponentと呼ぶことにする。

ここで、以下の処理を任意回数行える。

  • 任意のセル１か所の色を白黒反転させる。ただしその前後で以下の条件を満たすこと。
    • 処理の前後で白黒それぞれのcomponent数が増減しない。
    • 同じ色の異なるcomponentが角を共有しない。

この処理を繰り返すことで、initialで表現されるグリッドの状態をtargetで表現される状態に移行できるか答えよ。

解法

この問題の条件によると、処理前後でcomponent数が増減しないことから、連結成分をマージしたり分割したりできない。
また角の共有を許可しないことからcomponent同士が点で接することもできない。
また、1文字が実は10000*10000セルでできている、という条件は1文字分未満のサイズでセルを移動できることを意味する。

つまり、この問題はinitialとtargetがトポロジーでいう同相であることを示せと言っていることになる。
よって、initialとtargetにおけるcomponentの内包関係を何らかの形で表現し、それが一致することを示せばよい。

２次元座標上で内包関係は木で表現できることは明らかなので、まず白黒の各componentが互いに囲んでいる状態を木で表現しよう。
まず前処理としてUnion-Findなどでセルをcomponentに分類しておく。
次に、一番外側のcomponentから初めて、「未登場のcomponentに隣接したら、そのcomponentを包んでいると考える」という判定を再帰的に行えばよい。

initialとtargetからそれぞれ内包関係を表す木が表現できたら、次にこれが一致するか判定する。
そのまま木を表現する配列を一致判定してもダメである。
なぜなら、各頂点における子の登場順が両表現で一致するか不明のためである。

そこで、「各頂点における子の登場順」を何らかの基準で並べ替えればよい。
内包関係が一致するなら、この並べ替え処理を行った後の木の表現も一致するはずである。
以下に一例を示す。

  • 各頂点において、サブツリーのハッシュ値を考える。
  • 各頂点において、サブツリーの構成を括弧列（(()(()()))など）で表現する。
    • こちらも同様に葉から順に括弧列を生成する。
    • 子を持つ親頂点の括弧列は、子頂点のサブツリーの括弧列をソートし、その結果を連結したのち全体を"()"で囲って生成する。同型の木なら括弧列の中身は同じはずである。

以下のコードは前者である。

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;
	}
};

pair<ll,ll> tree_normalize(vector<int> T) {
	ll momo[2]={1000000007,1000000009};
	const int MP=5000,prime_max = 100000;
	static int prime[MP+10],NP,divp[prime_max+10];
	
	int i,j;
	if(NP==0) {
		for(i=2;NP<MP;i++) if(divp[i]==0) {
			assert(i<prime_max);
			if(i>5000) prime[NP++]=i;
			for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
		}
		assert(NP==MP);
	}
	
	vector<vector<pair<ll,ll>>> V;
	V.resize(T.size());
	for(i=T.size()-1;i>=0;i--) {
		V[i].push_back({1,1});
		sort(V[i].begin(),V[i].end());
		pair<ll,ll> p={0,0};
		FOR(j,V[i].size()) {
			(p.first+=V[i][j].first*prime[j])%=momo[0];
			(p.second+=V[i][j].second*prime[j])%=momo[1];
		}
		V[T[i]].push_back(p);
	}
	return V[0].back();
}



class Balance {
	public:
	int N;
	int vis[4000];
	UF<10000> uf;
	vector<int> mem[4000];
	
	
	void dfs(vector<int>& R,int id,int g) {
		int i;
		vector<int> c;
		vis[g]=1;
		FORR(r,mem[g]) {
			int cy=r/60,cx=r%60;
			FOR(i,4) {
				int dd[4]={1,0,-1,0};
				int ty=cy+dd[i],tx=cx+dd[i^1];
				if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
				int g2=uf[ty*60+tx];
				if(vis[g2]==0) vis[g2]=1, c.push_back(g2);
			}
		}
		int cur=R.size();
		R.resize(cur+c.size());
		FOR(i,c.size()) R[cur+i]=id, dfs(R,cur+i, c[i]);
	}

	vector<int> maketree(vector<string> S) {
		vector<vector<int>> D;
		int y,x;
		
		N=S.size()+2;
		D.resize(N);
		FOR(y,N) D[y].resize(N);
		FOR(y,N-2) FOR(x,N-2) D[y+1][x+1]=S[y][x]=='.';
		
		uf.reinit();
		ZERO(vis);
		
		FOR(y,N) FOR(x,N) {
			mem[y*60+x].clear();
			if(x<N-1 && D[y][x]==D[y][x+1]) uf(y*60+x,y*60+x+1);
			if(y<N-1 && D[y][x]==D[y+1][x]) uf(y*60+x,y*60+x+60);
		}
		FOR(y,N) FOR(x,N) mem[uf[y*60+x]].push_back(y*60+x);
		vector<int> R;
		R.push_back(0);
		dfs(R,0,uf[0]);
		return R;
	}
	
	string canTransform(vector <string> initial, vector <string> target) {
		vector<int> T[2];
		T[0]=maketree(initial);
		T[1]=maketree(target);
		
		if(tree_normalize(T[0])==tree_normalize(T[1])) return "Possible";
		return "Impossible";
	}
}

まとめ

木の同型判定、というかハッシュ値表現を求める関数はライブラリにしておこう。