第4回 ドワンゴからの挑戦状 予選 C - Kill/Death

問題概要

AチームとBチームにわかれて対戦するゲームがある。このゲームでは試合終了後に各プレイヤーのリザルトとしてkill数とdeath数が表示される。リザルトは各チームごとにkill数の多いプレイヤーから順に表示される。kill数が同数の場合はdeath数の少ない順になる。ある試合が終わったあとのAチーム(N人)のリザルトとBチーム(M人)のリザルトがkill数のみ表示された状態で与えられるので、ありうるdeath数の組合せが何通りあるか求めよ。ただしAチームのdeathはBチームのkillによってしか起こらず、BチームのdeathはAチームのkillによってしか起こらないものとする。

N, M <= 100, 各チームのkill数の合計 <= 1000

解法

もし「kill数が同数の場合はdeath数の少ない順になる」という制約がなければ、以下のようなDPで答えを求めることができる。

dp(i, j): i人目までにj個のdeathを割り当てたときの、deathの配り方

DPの遷移は単純にi人目に何個のdeathを配るかということになるので、0~sum(kill数の合計)を総当たりすればよい。このDPの計算量はO(N×sum(kill数)2)でおおよそ108くらいになる。このくらいであればやたら定数倍が重いデータ構造を使うのでもない限り間に合う範疇である(と感覚的には思っている)。

次に「kill数が同数の場合はdeath数の少ない順になる」という制約を入れた場合であるが、これも基本的には上のDPと同じ形で解くことができる。そのために必要な考え方は「ある人にdeathを1つ割り当てるとき、後ろに同じkill数の人たちが並んでいるのであれば、その人たちにも必ずdeathを1配ることにする」ということである。このような配り方をすると昇順のルールが崩れず、しかもdeathの割り当てを各人で独立に考えることができるようになる。

これを踏まえて上のDPを書き直すと、まずDPの状態は↑と同じである。遷移だけが少し変わっており、配るdeathの数を「自分+自分の後ろにいてkill数が同じ人の数」の倍数に限ることにする(これが「後ろのひとたちにも同じ数deathを配る」に当たる)。最終的にはdp(N, sum(kill数))が答えとなる。計算量は前述のものと同様。

追記(2018/1/21)

コメント欄で id:nanae1914 さんに全体の計算量が O(N×sum(kill数)2) から O(N×sum(kill数)) に落ちるDP遷移を教えてもらいました。これだと108が105に落ちるので圧倒的に間に合いますね(というか想定解をブチ抜いている)。詳しく書いていただいたのでぜひコメントの方を見てみてください。

感想

解けたはいいものの、分割数という概念をよく知らないので要勉強

コード

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

immutable long MOD = 10^^9+7;


long calc(int n, int[] a, int kills) {
    auto same = new long[](n);
    same[n-1] = 1;

    for (int i = n-2; i >= 0; --i) {
        if (a[i] == a[i+1]) same[i] = same[i+1]+1;
        else same[i] = 1;
    }

    auto dp = new long[][](n+1, kills+1);
    dp[0][0] = 1;

    foreach (i; 0..n) {
        foreach (j; 0..kills+1) {
            for (int k = 0; j + k <= kills; k += same[i]) {
                dp[i+1][j+k] += dp[i][j];
                dp[i+1][j+k] %= MOD;
            }
        }
    }

    return dp[n][kills];
}


void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto A = readln.split.map!(to!int).array;
    auto B = readln.split.map!(to!int).array;
    long ans = calc(N, A, B.sum) * calc(M, B, A.sum) % MOD;
    ans.writeln;
}