kmjp's blog

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

TopCoder SRM 724 Div1 Medium GravityPuzzle

こういうパズル珍しい。
https://community.topcoder.com/stat?c=problem_statement&pm=14743

問題

長方形のグリッドのうち、いくつかのマスがブロックで埋まっている。
この盤面を上下左右に傾けると、ブロックがその向きにそれ以上動けなくなるまで移動するものとする。

最終的な盤面の状況が与えられたとき、盤面を傾けてそのようにできる初期状態は何通りあるか。

解法

まず初期状態に関し、さらに傾けるとブロックが移動してしまう向きを調べよう。
例えば左に傾けるとブロックが移動してしまう場合、逆に最後左に傾けてこの状態を作ることができない。

最後移動できない向きが0,4の場合は初期状態=入力状態しかありえないので解は1。
上下がともに移動できる、またはどちらも移動できない場合、初期状態から左右方向の移動により条件を満たせるようになることになる。
その場合、各行において組み合わせ計算をすればよい。
左右が移動不可で上下に移動可能の状態も同様。

残るケースは、上下いずれか片方および左右いずれか片方に移動可能な状態である。
わかりやすくするため、盤面を回転して、すでにブロックが左上に固まっているケースを考えよう。
例えばこんな感じ。

##..
##..
#...
....
....

この状態を生成できる初期状態を考えよう。
初期状態から左に傾け、その後上に傾けてこの状態にできる条件を考えよう。
各行のブロック数が2,2,1,0,0(順不同)であればそうできるので、組み合わせ計算で求めよう。

また、初期状態から上に傾け、その後左に傾けてこの状態にできる条件を同様に考えよう。
こちらは各列のブロックが3,2,0,0(順不同)であればよい。

ただ、上記の数え上げでは左と上どちらを先に移動しても条件達成できるケースが二重にカウントされているのでそれらを取り除こう。
この状態では、ブロックは横2列縦3行を占めている。
結果だけ言えば、条件を満たすのは以下の通り。

  • 初期状態でブロックが存在するのは、終了状態と同じどこか2列とどこか3列
  • ブロックがある2列・3行に関しては、列の入れ替えまたは行の入れ替えを行ってもよい。

これらは同様に組み合わせ計算で求められる。

ll mo=1000000007;
const int CN=401;
ll C[CN][CN];

class GravityPuzzle {
	public:
	int H,W;
	int count(vector <string> B) {
		H=B.size();
		W=B[0].size();
		int i,j;
		FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
		
		int U=1,D=1,L=1,R=1;
		int y,x;
		int sum=0;
		FOR(y,H) FOR(x,W) B[y][x]=(B[y][x]=='#');
		FOR(y,H) FOR(x,W) if(B[y][x]==1) {
			sum++;
			if(y&&B[y-1][x]==0) U=0;
			if(y<H-1&&B[y+1][x]==0) D=0;
			if(x&&B[y][x-1]==0) L=0;
			if(x<W-1&&B[y][x+1]==0) R=0;
		}
		if(L+R+U+D==4) return 1;
		if(L+R+U+D==0) return 1;
		if(L+R==2 || L+R==0) {
			ll ret=1;
			if(U+D==0) return 1;
			FOR(x,W) {
				int cnt=0;
				FOR(y,H) cnt+=B[y][x];
				(ret *= C[H][cnt])%=mo;
			}
			return ret;
		}
		if(U+D==2 || U+D==0) {
			ll ret=1;
			if(L+R==0) return 1;
			FOR(y,H) {
				int cnt=0;
				FOR(x,W) cnt+=B[y][x];
				(ret *= C[W][cnt])%=mo;
			}
			return ret;
		}
		
		FOR(y,H) {
			FOR(x,W) cout<<(B[y][x]?'#':'.');
			cout<<endl;
		}
		
		ll ret[3]={1,1};
		int cnt[2][55]={};
		FOR(x,W) {
			int d=0;
			FOR(y,H) d+=B[y][x];
			cnt[0][d]++;
			(ret[0]*=C[H][d])%=mo;
		}
		FOR(y,H) {
			int d=0;
			FOR(x,W) d+=B[y][x];
			cnt[1][d]++;
			(ret[1]*=C[W][d])%=mo;
		}
		int nw=0,nh=0;
		ll a=1,b=1;
		for(i=0;i<=51;i++) {
			nw+=cnt[0][i];
			(a*=C[nw][cnt[0][i]])%=mo;
			nh+=cnt[1][i];
			(b*=C[nh][cnt[1][i]])%=mo;
		}
		
		
		return ((ret[0]*a+ret[1]*b-a*b)%mo+mo)%mo;
		
	}
}

まとめ

コーナーケースの面倒くささはともかく、それを除けばシンプルで良い問題。