Codeforces #179 Div2 E "Greg and Friends"
問題
http://codeforces.com/contest/296/problem/E
訳
n人が船を使って川を渡ろうと考えている。
船はひとつしかなく、重量制限はkキロまでとなっている。
n人の体重を紙に書いてみると、50kgか100kgのどちらかである事が判明した。
船で川を渡る回数を最小にし、n人全員を対岸へ移動させる時、
その方法がどれだけあるかが知りたい。
船を無人で対岸へ向かわす事はできない
船で川を渡るときに、そこに乗っていた人の構成が違っていれば、
違う方法とみなす。
制約
1 <= n <= 50
1 <= k <= 5000
考えた事
状態の数は意外と少ないような・・・
船が川を何回渡って、船がある岸に50kgの人が何人いて、100kgの人が何人いるか?
a0 = 50kgの人数
b0 = 100kgの人数
count = 川を渡った回数
a1 = 船のある岸にいる50kgの人数
b1 = 船のある岸にいる100kgの人数
a2 = これから船にのる50kgの人数
b2 = これから船にのる100kgの人数
xCy = C[x][y]
とすると、
対岸の50kgの人数 = a3 = a0 - a1 + a2
対岸の100kgの人数 = b3 = b0 - b1 + b2
dp[ count+1 ][ a3 ][ b3 ] += dp[ count ][ a1 ][ b1 ] * C[ a1 ][ a2 ] * C[ b1 ][ b2 ]
となる。
ここで、countが奇数のときは目標となる岸を意味するので
dp[ count ][ a0 ][ b0 ] != 0 となった時、それを出力する。
countは何回までやればいいか?
最も回数がかかってしまうケースは、
50kgが2人、100kgが48人、kが100~149の場合で、(だぶん・・・)
50 50 100 100... 50 50 100 100 ... 50 50 100 100 ... 50 100 50 100 ... 100 50 50 100 ...
上記のように、100kgの人を1人対岸に送るのに4往復かかるので、
200回やってもダメなら不可能と考えてよい。
状態数は最大で、200 * 25 * 25
各状態の更新は最大で、25 * 25なので、
計算量は200 * 25^4 = 8000万ぐらい?
ソースコード
const int MOD = 1000000007; long long C[55][55]; // iCj mod MOD int N, K; int a0, b0; long long dp[205][55][55]; long long mod_pow( int a, int b ){ if( b == 1 ) return a; if( b % 2 ){ long long r = mod_pow( a, b-1 ); return a * r % MOD; }else{ long long r = mod_pow( a, b/2 ); return r * r % MOD; } } long long mod_inv( int a ){ return mod_pow( a, MOD - 2 ); } int main() { // Cを初期化 C[0][0] = 1; for( int i = 1; i <= 50; i++ ){ C[i][0] = 1; for( int j = 1; j <= i; j++ ){ C[i][j] = C[i][j-1] * (i - j + 1) % MOD * mod_inv( j ) % MOD; } } // 入力 cin >> N >> K; a0 = b0 = 0; for( int i = 0; i < N; i++ ){ int kg; cin >> kg; if( kg == 50 ) a0++; if( kg == 100 ) b0++; } // dp初期化 memset( dp, 0, sizeof(dp) ); dp[0][a0][b0] = 1; // dp更新 for( int count = 0; count <= 200; count++ ){ for( int a1 = 0; a1 <= a0; a1++ ){ for( int b1 = 0; b1 <= b0; b1++ ){ long long base = dp[count][a1][b1]; for( int a2 = 0; a2 <= a1; a2++ ){ for( int b2 = 0; b2 <= b1; b2++ ){ if( a2 == 0 && b2 == 0 ) continue; // 無人はダメ if( a2 * 50 + b2 * 100 > K ) continue; // 重量オーバー long long add = base * C[a1][a2] % MOD * C[b1][b2] % MOD; int a3 = a0 - a1 + a2; int b3 = b0 - b1 + b2; dp[count+1][a3][b3] += add; dp[count+1][a3][b3] %= MOD; } } } } // dp[count+1][a0][b0] != 0であれば出力 if( ((count+1) % 2) && (dp[count+1][a0][b0] != 0) ){ printf( "%d\n", count+1 ); printf( "%I64d\n", dp[count+1][a0][b0] ); return 0; } } // 不可能 //printf( "%s\n", "impossible" ); printf( "%d\n", -1 ); printf( "%d\n", 0 ); return 0; }