Coder-Strike 2014 Round2 - D. 2048

ARCでも先日2048が出たけど、こちらでも出てきた。
GCJもCookie Clickerネタが出てきたし、流行ネタが多いね。
なかなか面白い良問。
http://codeforces.com/contest/413/problem/D

問題

１列に並んだのマス目に２または４の数値が書かれている。

これらを左に傾けると各マスの数字は以下のように動き、それ以上変化が起きなくなるまで以下の動作を繰り返す。

• 一番左のマスはそれ以上動かない
• 他のマスは、左に同じ大きさの数字があれば２つが合体して倍の数字の１マスになる
• 左のマスが異なる数字ならそれ以上動かない

初期状態のマスの状態が与えられる。
初期状態は2,4,不定のいずれかであり、不定は2または4が入る。
上記動作を行った場合、数Kに対し2^Kが作れるような初期状態の組み合わせ数を答えよ。

解法

2から開始だと分かりにくいので、全体を2で割って1,2,不定で初めて2^(K-1)を作るとしよう。
小さい数字のマスの右に大きな数字が来た場合、その２つは今後絶対に合体しない。
逆に大きな数字のマスの右に小さな数字が来た場合、さらに小さな数字が来て小さな数字同士合体することで、２つは合体する可能性がある。

左端のマスからDPしていき、各マスの左側にあるマスの状態をbitmaskで持つことにする。
例えば101001なら左に32,8,1があるとする。
このmaskに新たに1,2のマスを右からぶつけると、以下のように変化する。

• 1のマスをぶつけるとmask全体に1を加算する
• 2のマスをぶつけた場合：
  • mask%2==1、すなわり右端のマスが1なら、そこは二度とくっつかないので、mask=2で置き換える。
  • mask%2==0なら、mask全体に2を加算する

maskが2^(K-1)を超えたら、そこまでのマスで2^(K-1)が作れることになるので、その分を解答に加算する。
また、途中で0が出てきたらそこまで加算した解答を倍に出来る(0の実体が1でも2でもその左側で2^(K-1)を作れるため)

右に数字をぶつけるという動作が、結果的にbitmaskに加算するのと同じだと表現できる点が面白い。

int N,K;
int A[3000];
ll mo=1000000007;

ll dpdp[2001][1<<12];
int next[1<<12][2];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K;
	K--;
	FOR(i,N) cin>>A[i], A[i]/=2;
	
	ll ret=0;
	dpdp[0][0]=1;
	FOR(i,N) {
		if(A[i]==0) ret=ret*2%mo;
		for(int mask=0;mask<1<<K;mask++) {
			
			if(A[i]==1 || A[i]==0) {
				if(mask+1>=1<<K) ret+=dpdp[i][mask];
				else dpdp[i+1][mask+1]=(dpdp[i+1][mask+1]+dpdp[i][mask])%mo;
			}
			if(A[i]==2 || A[i]==0) {
				if(mask&1) {
					dpdp[i+1][2]+=dpdp[i][mask];
				}
				else {
					if(mask+2>=1<<K) ret+=dpdp[i][mask];
					else dpdp[i+1][mask+2]=(dpdp[i+1][mask+2]+dpdp[i][mask])%mo;
				}
			}
			
		}
	}
	cout << ret%mo << endl;
}

まとめ

せっかくFirst Answerのチャンスなのに、最後 % moをつけ忘れた…。
bitDPであることはKの制限からすぐ推測できたけど、bitmaskに加算するだけ、というのは2048を実際にプレイしていたからすぐ思いつけた気がする。