TopCoder SRM 605 Div1 Medium AlienAndSetDiv1、Div2 Hard AlienAndSetDiv2

本番は見当違いのアプローチをして落としてしまった。
Div1とDiv2は若干異なるがほぼ同じ。
http://community.topcoder.com/stat?c=problem_statement&pm=12980
http://community.topcoder.com/stat?c=problem_statement&pm=12954

問題

1～2Nの数字を２つの配列A,BにN個ずつ振り分ける。
A,Bは振り分けられた数字を昇順に格納する。
ここで数字Kに対し、A,Bは以下の条件を満たさなければならない。

• Div1 Medium: |A[i]-B[i]|>=K
• Div2 Hard: |A[i]-B[i]|<=K

N,Kに対し、そのような振り分けかたの組み合わせ数を答えよ。

解法

ほぼ同じなので、Div1 Mediumについて書いていく。
1から順にA,Bに振り分けていくことを考える。
この時、DPの状態として[Aに入れた要素数][Bに入れた要素数][直前K個の履歴のbitmap]を持たせてDPする。

各状態について、次の数字pをA,Bどちらに入れるか考える。
例えば下記の状態ならpはAに入れることができる。

• AがすでにN個入っているなら不可
• Aの要素数がBの要素数以上なら可
• Aの要素数がBの要素数未満の場合、pをAに追加したときに対応するB[i]との差がK以上なら可

最後の条件については、A,Bの要素数とK個のbitmapからB[i]の数値を求めることができる。
B[i]がK個のbitmapからはみ出てK個以上前に積まれた数字の可能性もあるが、その時はK以上の差があるのは明らかなので問題ない。

Div2の方は、最後の条件を「B[i]との差がK以下」に直せばよい。
ただ、直前K個ではなく(K+1)個をbitmapで保持してB[i]を求める必要がある。

ll mo=1000000007;
ll dpdp[52][52][1<<10];
class AlienAndSetDiv1 {
	public:
	
	int getNumber(int N, int K) {
		int i,x,y,mask,mask2=(1<<K)-1;
		ll ret=0;
		ZERO(dpdp);
		dpdp[0][0][0]=1;
		FOR(x,N+1) FOR(y,N+1) FOR(mask,1<<K) {
			if(x+y>=2*N) continue;
			ll va=dpdp[x][y][mask];
			int nex=x+y+1;
			
			bool addadd=false;
			//push A
			if(x<N && x>=y) addadd = true;
			if(x<y) {
				int y2=y,va=nex;
				FOR(i,K) {
					va--;
					if((mask>>i)&1) {
						if(y2==x+1) break;
						y2--;
					}
				}
				addadd = (nex-va>=K);
			}
			
			if(addadd) dpdp[x+1][y][((mask<<1)&mask2)] = (dpdp[x+1][y][((mask<<1)&mask2)]+va) % mo;
			
			//push B
			addadd=false;
			if(y<N && y>=x) addadd = true;
			if(y<x) {
				int x2=x,va=nex;
				FOR(i,K) {
					va--;
					if(((mask>>i)&1)==0) {
						if(x2==y+1) break;
						x2--;
					}
				}
				addadd = (nex-va>=K);
			}
			if(addadd) dpdp[x][y+1][1+((mask<<1)&mask2)] = (dpdp[x][y+1][1+((mask<<1)&mask2)]+va) % mo;
		}
		
		FOR(mask,1<<K) ret+=dpdp[N][N][mask];
		return ret%mo;
	}
}

class AlienAndSetDiv2 {
	public:
	int getNumber(int N, int K) {
		int i,x,y,mask,mask2=(1<<(K+1))-1;
		ll ret=0;
		ZERO(dpdp);
		dpdp[0][0][0]=1;
		FOR(x,N+1) FOR(y,N+1) FOR(mask,1<<(K+1)) {
			if(x+y>=2*N) continue;
			ll va=dpdp[x][y][mask];
			int nex=x+y+1;
			
			bool addadd=false;
			//push A
			if(x<N && x>=y) addadd = true;
			if(x<y) {
				int y2=y,va=nex;
				FOR(i,K+1) {
					va--;
					if((mask>>i)&1) {
						if(y2==x+1) break;
						y2--;
					}
				}
				addadd = (nex-va<=K);
			}
			
			if(addadd) dpdp[x+1][y][((mask<<1)&mask2)] = (dpdp[x+1][y][((mask<<1)&mask2)]+va) % mo;
			
			//push B
			addadd=false;
			if(y<N && y>=x) addadd = true;
			if(y<x) {
				int x2=x,va=nex;
				FOR(i,K+1) {
					va--;
					if(((mask>>i)&1)==0) {
						if(x2==y+1) break;
						x2--;
					}
				}
				addadd = (nex-va<=K);
			}
			if(addadd) dpdp[x][y+1][1+((mask<<1)&mask2)] = (dpdp[x][y+1][1+((mask<<1)&mask2)]+va) % mo;
		}
		
		FOR(mask,2<<K) ret+=dpdp[N][N][mask];
		return ret%mo;
	}
}

まとめ

本番は違うアプローチに行って失敗していたのでしょうがないか。
K<=50と見誤ったためbitDPが最初から候補に入ってなかった…。