Codeforces #1021 : Div1 B. Baggage Claim

まぁまぁ出来の良かった回。
https://codeforces.com/contest/2097/problem/B

問題

H*Wのグリッドにおいて、重複しない隣接マスをたどる(2K+1)マスからなるパスを考える。
この時、このパスにおける奇数番目のマスの位置が与えられる。
偶数番目のマスの配置は何通り可能か。

解法

まず、奇数番目のマスは順番に2マスずつ離れていないといけない。
その際、2n-1番目と2n+1番目のマスが縦または横に2マス離れているとき、間のマスの配置は確定する。

2n-1番目と2n+1番目のマスが斜めにある場合、間のマスは2つ選択肢がある。
各マスに対応する頂点を持つグラフを考え、2つのマスを辺でつなごう。
各連結成分について、n辺に対し

• 空きマスが(n+1)個あるなら、その連結成分内のマスの配置は(n+1)通り
• 空きマスがn個あるとき
  • 残り1個が確定マスなら、その連結成分内のマスの配置は1通り
  • 残り1個が確定マスでないなら、その連結成分内のマスの配置は2通り
• 空きマスがn個未満のとき、その連結成分内のマスの配置は0通り

int T,H,W,K;
const ll mo=1000000007;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	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 num=um) {int i; FOR(i,num) 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;
	}
};
UF<1<<20> uf;
vector<int> C[1<<20],D[1<<20],F[1<<20];
int X[1<<20],Y[1<<20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K;
		uf.reinit(H*W);
		FOR(y,H) {
			C[y].clear();
			C[y].resize(W);
			D[y].clear();
			D[y].resize(W);
			F[y].clear();
			F[y].resize(W);
		}
		int ok=1;
		FOR(i,K+1) {
			cin>>Y[i]>>X[i];
			Y[i]--;
			X[i]--;
			C[Y[i]][X[i]]++;
		}
		FOR(i,K) if(ok) {
			if(abs(Y[i]-Y[i+1])+abs(X[i]-X[i+1])!=2) {
				ok=0;
				break;
			}
			if(Y[i]==Y[i+1]) {
				if(C[Y[i]][(X[i]+X[i+1])/2]++) ok=0;
			}
			if(X[i]==X[i+1]) {
				if(C[(Y[i]+Y[i+1])/2][X[i]]++) ok=0;
			}
		}
		FOR(i,K) if(Y[i]!=Y[i+1]&&X[i]!=X[i+1]) {
			if(C[Y[i]][X[i+1]]) {
				if(C[Y[i+1]][X[i]]) {
					ok=0;
				}
				else {
					D[Y[i+1]][X[i]]++;
					F[Y[i+1]][X[i]]++;
				}
			}
			else if(C[Y[i+1]][X[i]]) {
				D[Y[i]][X[i+1]]++;
				F[Y[i]][X[i+1]]++;
			}
			else {
				D[Y[i]][X[i+1]]++;
				uf(Y[i]*W+X[i+1],Y[i+1]*W+X[i]);
			}
		}
		
		ll ret=ok;
		FOR(i,H*W) if(uf[i]!=i) {
			D[uf[i]/W][uf[i]%W]+=D[i/W][i%W];
			F[uf[i]/W][uf[i]%W]+=F[i/W][i%W];
		}
		FOR(i,H*W) if(uf[i]==i) {
			y=i/W,x=i%W;
			if(D[y][x]==0) continue;
			if(uf.count(i)<D[y][x]) ret=0;
			if(uf.count(i)>D[y][x]) ret=ret*uf.count(i)%mo;
			if(uf.count(i)==D[y][x]&&F[y][x]==0) ret=ret*2%mo;
		}
		cout<<ret<<endl;
	}
}

まとめ

割とシンプルな設定と難易度で、B問題としてはちょうど良さそう。