WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}