Codeforces 118D: Caesar's Legions

Problem - 118D - Codeforces

Difficulty: 1800

シンプルなDP．多分どうやっても解ける感じの問題だが，状態数が多いのでスマートに実装を行わないと沼にハマる．

問題概要

n1人の歩兵とn2人の騎兵を一列に並べる．歩兵はk1人を超えて連続してはならず，騎兵はk2人を超えて連続してはならない． 歩兵同士，騎兵同士の区別はできないとき，条件を満たす並べ方の場合の数を求めよ．

n1 = n2 = 100, k1 = k2 = 10

解法1

自分がやったやり方．実装が辛くてバグりまくったので，センスは良くない．

次のようなDPテーブルを考える．

dp[i][j][k][l] := i番目まで見て，騎兵(l=1)または歩兵(l=0)がj人連続しており，まだ並べていない歩兵がk人いるような，条件を満たす場合の数

配るDPを考え，次に歩兵を並べる遷移，騎兵を並べる遷移を考えれば良い．実装は以下の通り．

    mint dp[210][210][110][2] = {};

    int n1,n2,k1,k2; cin >>n1>>n2>>k1>>k2;
    dp[0][0][n1][0].x = 1;
    for(int i = 0; i < n1+n2; i++){ //配るDP
        for(int l = 0; l < 2; l++){
            if(l == 0){ // 連続しているのが歩兵の場合
                for(int j = 0; j < k1; j++){
                    for(int k = 1; k <= n1; k++){
                        dp[i+1][j+1][k-1][l] += dp[i][j][k][l]; //歩兵→歩兵
                    }
                }
                for(int j = 0; j <= k1; j++){
                    for(int k = 0; k <= n1; k++){
                        dp[i+1][1][k][1] += dp[i][j][k][l]; //歩兵→騎兵
                    }
                }

            }else{ //　連続しているのが騎兵の場合
                for(int j = 0; j< k2; j++){
                    for(int k = 0; k <= n1; k++){
                        dp[i+1][j+1][k][l] += dp[i][j][k][l]; //騎兵→騎兵
                    }
                }

                for(int j = 0; j <= k2; j++){
                    for(int k = 1; k <= n1; k++){
                        dp[i+1][1][k-1][0] += dp[i][j][k][l]; //騎兵→歩兵
                    }
                }

            }
        }

    }

    mint ans = 0;
    REP(j,110){
        REP(l,2){
            ans += dp[n1+n2][j][0][l];
        }

    }
    cout << ans.x << endl;

解法2

Codeforces 118 D: Caesar’s Legions – mplancer を参考にした．

DP[i][j][k][l] := 今歩兵がk人，または騎兵がl人連続しており，残り歩兵i人と騎兵j人を並べる並べ方で，条件を満たす場合の数

メモ化再帰でシンプルに書ける．美しい

mint dp[110][110][15][15] = {};
int k1,k2;

mint solve(int n1, int n2, int x1, int x2){
    if(n1 == 0 && n2 == 0) return 1;
    mint res = dp[n1][n2][x1][x2];
    if(res.x != -1) return res;
    res = 0;
    if(n1 > 0 && x1 < k1){
        res += solve(n1-1,n2,x1+1,0);
    }
    if(n2 > 0 && x2 < k2){
        res += solve(n1,n2-1,0,x2+1);
    }
    dp[n1][n2][x1][x2] = res;
    return res;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    REP(i,110) REP(j,110) REP(k,15) REP(l,15){
        dp[i][j][k][l] = -1;
    }
    int n1,n2;
    cin >> n1 >> n2 >> k1 >> k2;
    cout << solve(n1,n2,0,0).x << endl;
}