kmjp's blog

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

第四回 アルゴリズム実技検定 : N - マス目の穴埋め

これも割とすんなり解いているな。
https://atcoder.jp/contests/past202010-open/tasks/past202010_n

問題

18x6のグリッドを0/1で埋めることを考える。初期状態で各セルは0/1/?のいずれかである。
?の部分をそれぞれ0/1のいずれかで埋めたとき、以下を満たす組み合わせは何通りか。

  • 各マスの値は、そのマスと上下左右のマスの5値の中央値に等しい。

解法

上2行分の値をbitmaskで持ちながらDPしていく。
上2行の値が定まると、次の行に取りえる選択肢がかなり狭まるので、あらかじめ選択肢を列挙しておくとTLEせずに済む。

vector<int> ok[1<<6][1<<6];

ll from[1<<6][1<<6];
ll to[1<<6][1<<6];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int m1,m2,m3;
	FOR(m1,1<<6) FOR(m2,1<<6) FOR(m3,1<<6) {
		int c=1;
		FOR(y,6) {
			x=0;
			x+=(m1>>y)&1;
			x+=(m3>>y)&1;
			x+=(m2>>y)&1;
			x+=(m2>>(y+1))&1;
			if(y) x+=(m2>>(y-1))&1;
			if(x>=3&&(m2&(1<<y))==0) c=0;
			if(x<3&&(m2&(1<<y))) c=0;
		}
		if(c) ok[m1][m2].push_back(m3);
	}
	FOR(m1,1<<6) from[0][m1]=1;
	FOR(i,18) {
		ZERO(to);
		cin>>s;
		FOR(m2,1<<6) {
			int c=1;
			FOR(y,6) {
				if(s[y]=='0'&&((m2>>y)&1)) c=0;
				if(s[y]=='1'&&((m2>>y)&1)==0) c=0;
			}
			if(c==0) continue;
			FOR(m1,1<<6) FORR(p,ok[m1][m2]) to[m2][p]+=from[m1][m2];
		}
		swap(from,to);
	}
	ll ret=0;
	FOR(m1,1<<6) ret+=from[m1][0];
	cout<<ret<<endl;
}

まとめ

これなんで縦横の幅固定にしてるんだろうな。