Codeforces #179 Div1. C. Greg and Friends

さて、本番中に何とか解けたC。
http://codeforces.com/contest/295/problem/C

問題

N人の人間をKキログラムまで乗れるボートを使って対岸に運ぶ。
ボートを動かすには、最低１人以上の人間を運ぶ必要があり、かつ人間の重さの合計はKキログラム以下でなければならない。

全員を対岸に運ぶまでに動かすボートの回数の最小値と、その時の手順の組み合わせ数を求めよ。
なお、人の重さは50kgか100kgのいずれかである。

解法

まず、重さは50kgか100kgなので、Kも合わせて50で割ってしまう。
あとは、重さが1の人数と2の人数を使ってDPしていく。

こちらの岸と対岸交互に、重さが1の人数と2の人数の中から1人以上・重さK以下になるように全移動パターンを行ってDPする。
このとき、重さが1の中から数名と2の中から数名選ぶので、組み合わせ数を掛け合わせていく。

このDPを繰り返し、対岸に全員が集合したタイミングで終了、その組み合わせを答える。
Kの値によっては全員を対岸に連れて行くことが不可能だが、人の人数は50名までなので200回位やり取りを繰り返して対岸に人が集まらなければ不可能と判定してよい。

int N,K;
int W[1000];
int NP[2];

ll MP[202][52][52];
ll MO=1000000007;
ll C[60][60];
void solve() {
	int f,r,i,j,k,l,x,y,mp,loop,px,py;
	ll t;
	
	ZERO(C);
	C[0][0]=1;
	for(x=1;x<60;x++){
		C[x][0]=C[x][x]=1;
		for(y=1;y<x;y++) C[x][y]=(C[x-1][y-1]+C[x-1][y])%MO;
	}
	
	N=GETi();
	K=GETi()/50;
	FOR(i,N) {
		W[i]=GETi()/50;
		NP[W[i]-1]++;
	}
	
	ZERO(MP);
	MP[0][NP[0]][NP[1]]=1;
	
	FOR(loop,202) {
		MP[loop+1][NP[0]][NP[1]]=MO;
		FOR(x,NP[0]+1) FOR(y,NP[1]+1) {
			if(MP[loop][x][y]==0) continue;
			FOR(px,x+1) FOR(py,y+1) {
				if(px+py==0) continue;
				if(px+py*2<=K) MP[loop+1][NP[0]-x+px][NP[1]-y+py] = 
					(MP[loop+1][NP[0]-x+px][NP[1]-y+py]+MP[loop][x][y]*((C[x][px]*C[y][py])%MO)) % MO;
			}
		}
		
		if(loop%2==0 && MP[loop+1][NP[0]][NP[1]]!=MO) {
			_P("%d\n%d\n",loop+1,(int)MP[loop+1][NP[0]][NP[1]]);
			return;
		}
	}
	
	_P("-1\n0\n");
	return;
}

まとめ

ちょっとややこしいDPだけど無事解けて良かった。
２つの岸を交互に処理する、というDPは新鮮だ。