Codeforces Round #333 (Div. 1) C. Kleofáš and the n-thlon

問題

codeforces.com

解法

Kleofáš のランクの合計が S であるとしましょう。すると, 結局求めるべきなのは n 試合終わった後にランクの合計が S 未満であるような人の数の期待値です。ということで, 以下のような dp を考えます。

dp[i][j] = (i 試合終わった後に ランクの合計が j であるような人の数の期待値)

この dp の更新式は,

dp[i+1][j] = (dp[i][j-1] + dp[i][j-2] + ... + dp[i][j-m]) / (m-1) - dp[i][j-X[i]] / (m-1)

となります。i 試合終わった時点でのランクの合計が j-x であるような人が次の試合でランクが x になる確率は 1/(m-1) であるので, 期待値的に dp[i][j-x] 人ランクの合計が j-x である人がいるなら, それらの人のうち誰かがランク x になる確率は dp[i][j-x]/(m-1) ということです。

ただ, Kleofáš 君が取ったランクを取ることは出来ないので dp[i][j-X[i]]/(m-1) は引いておこう, という感じです。

ただ, この更新式は O(m) かかり, dp の状態量 n*nm と比べると, ちょい厳しいです。実際には dp[i+1][j] を計算する時 dp[i+1][j] が 0 以外の値を取る可能性のある j の範囲は i+1 <= j <= (i+1)*m であるので, O(nm^2) となりますが, TL が 1 秒であることを考えると厳しそうです。なので, 以下のような工夫をしましょう。

sum という変数を用意して, sum = dp[i][j-1] + dp[i][j-2] + ... + dp[i][j-m] を保持するようにしておきます。これで dp[i+1][j] は求められますが, dp[i+1][j+1] を求めたいときは, sum に dp[i][j] を加えて, dp[i][j-m] を引くようにすれば, dp[i][j] + dp[i][j-2] + ... + dp[i][j-m+1] が得られ, O(1) で dp の更新式を計算できます。

const int MAXN = 101, MAXM = 1001;
double dp[MAXN][MAXM*MAXN];
int X[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    int S = 0;
    for (int i = 0; i < n; i++) {
        cin >> X[i];
        S += X[i];
    }
    dp[0][0] = m-1;
    for (int i = 1; i <= n; i++) {
        double sum = 0;
        for (int j = i; j <= i*m; j++) {
            sum += dp[i-1][j-1]/(m-1);
            if (j-m > 0) sum -= dp[i-1][j-m-1]/(m-1);
            dp[i][j] = sum;
            if (j-X[i-1] >= 0) dp[i][j] -= dp[i-1][j-X[i-1]]/(m-1);
        }
    }
    double ans = 1;
    for (int i = 0; i < S; i++) ans += dp[n][i];
    printf("%.10lf\n", ans);
    return 0;
}