AtCoder Regular Contest 061 F - 3人でカードゲーム / Card Game for Three

問題

arc061.contest.atcoder.jp

解法

まず普通に解法を考えます。一度それぞれのカードを決めたらすでにゲームの勝敗は決まっていることを考えるとなんか dp ではないような気がします。で, 問題の性質をよく考えると A さんが勝つには A さんに N 回ターンが回ってくれば良いことに気付きます。また, B, C が勝たないためには, B, C さんにそれぞれ M+1 回, K+1 回, ターンが回ってきてはいけないことに気付きます。つまり, 解法としては,

• 'b' が M+1 回, 'c' が K+1 回出る前に 'a' が N 回出るような N+M+K 枚のカードの並べ方は何通りあるか？

という問題に帰着します。

まず部分点のほうを考えましょう(下のコードでコメントアウトされているのがそれです)。
'b', 'c' の出る回数をそれぞれ m, k とします。この場合は, 'b' が m 回, 'c' が k 回, 'a' が N-1 回出たのちに 'a' が 1 回出る, で後はどうなっていても良い, という感じになるので,
comb[N-1+m+k][N-1] * comb[m+k][m] * 3^(M+K-m-k)
通りあります。これを m, k 全ての場合について数えれば良いです。

次に満点解法のほうを考えます。上の式をよく見ると, 「m+k」というのがいろんなところに出ていて, comb[m+k][m] の m, k に対する和さえ求められれば後は m+k に関する式になっているので m+k について全探索するだけで行けることに気付きます。

ということで comb[m+k][m] の m に関する和を求める方法を考えます。M=2, K=4 の場合について和を求める場所を考えると下の図のようになています。

i 行目から i+1 行目の和を考える際には, 漸化式 comb[n+1][r] = comb[n][r] + comb[n][r-1] を考えると, i+1 行目に移るときほとんど和が 2 倍になっていることが分かります。端っこのところだけ微妙にずれることがありますが, そこは適当にうまくやります。

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, m-2, m);
}

const int MOD = 1e9+7;
const int MAX = 1000000;
ll fact[MAX], rfact[MAX];
ll p3[MAX];

ll nCr(int n, int r) {
    return fact[n]*rfact[r]%MOD*rfact[n-r]%MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = i*fact[i-1]%MOD;
        rfact[i] = mod_inverse(fact[i], MOD);
    }
    p3[0] = 1;
    for (int i = 1; i < MAX; i++) {
        p3[i] = p3[i-1]*3%MOD;
    }
    int N, M, K;
    cin >> N >> M >> K;
    ll ans = 0;
    // for (int m = 0; m <= M; m++) {
    //     for (int k = 0; k <= K; k++) {
    //         ll tmp = fact[N-1+m+k];
    //         (tmp *= rfact[N-1])%=MOD;
    //         (tmp *= rfact[m])%=MOD;
    //         (tmp *= rfact[k])%=MOD;
    //         (tmp *= p3[M+K-m-k])%=MOD;
    //         (ans += tmp) %= MOD;
    //     }
    // }
    ll sum = 1;
    int low = 0, high = 0;
    for (int i = 0; i <= M+K; i++) {
        ans += nCr(N-1+i, N-1)*sum%MOD*p3[M+K-i]%MOD;
        int nh = min(i+1, M);
        int nl = max(0, i+1-K);
        sum = 2*sum;
        if (low < nl) sum -= nCr(i, low);
        if (high == nh) sum -= nCr(i, high);
        sum = (sum%MOD+MOD)%MOD;
        high = nh;
        low = nl;
    }
    ans %= MOD;
    cout << ans << endl;
    return 0;
}