ABC342-F Black Jack - zawatinはてなブログ

コンテスト中は丁寧丁寧丁寧に解いたので雑に雑に雑に解説残しておきます。想定解と多分一緒です。

問題概要

https://atcoder.jp/contests/abc342/tasks/abc342_f

あなたとディーラー、 $D$ 面サイコロ、変数 $x = 0, y = 0$ があります。あなたとディーラーがゲームをします。

まず、あなたが、以下の操作を好きな回数繰り返します。

サイコロを一回振る。出た目を $x$ に加算する。

次に、ディーラーが $y \lt L$ の間以下を繰り返します。

サイコロを一回振る。出た目を $y$ に加算する。

勝敗は次のように決められます。

$x \gt N$ ならディーラーの勝ち
そうでなくて $y \gt N$ ならあなたの勝ち
そうでなくて $x \gt y$ ならあなたの勝ち
そうでないならディーラーの勝ち

あなたが勝つために最適に行動した時、勝つ確率を求めてください。

制約

$1\ \le\ L\ \le\ N\ \le\ 2\times 10^{5}$
$1\ \le\ D\ \le\ N$

解法

dpを考えました。 $\text{dp}_{i}$ を「 $x$ の初期値が $i$ だったとしてゲームをはじめてあなたが勝つ確率」

$\text{dp}_{i}\ (i\ \gt\ N)$ の値はゲームのルールより $0$ です。(所謂dpの初期値)

そうで無い時、あなたはサイコロを振るか振らないかの二手があり、サイコロを振った場合の勝率と振らなかった場合の勝率が求まれば良いです(勝率が高い戦略を実際に選ぶことになる)。

サイコロを振った時の勝率は $\displaystyle \frac{1}{D}\sum_{j = 1}^{D} \text{dp}_{i + j}$

サイコロを振らなかった時の勝率は、 $y = j$ となる確率を $Y_{j}$ として $\displaystyle \sum_{k = N + 1}^{\infty} Y_{k} + \sum_{k = 0}^{i - 1} Y_{k}$ です。

$\text{dp}_{i}$ を計算するのに、 $\text{dp}_{i + 1}$ 以降のみが必要になることから $\text{dp}$ が後ろから計算できることがわかります。
サイコロを振った時の遷移は後ろ $D$ 個の $\text{dp}$ の和を別の変数で管理しておけばクリア
サイコロの振らなかった時の遷移は $Y$ さえ求まっていればその累積和を持ってクリア

サイコロを振らなかった時の遷移の計算に必要な $Y$ を求めましょう。明らかに $Y_{i} = 0\ (i\ \lt\ N\ \text{or}\ i\ \ge\ L + D)$ です*1。 $y$ が $i$ になっている瞬間がある確率を $Y'_{i}$ として、 $\displaystyle Y_{i} = \sum_{j = \max(1, i - L - 1)}^{\min(i, D)} Y'_{j}$ です。じゃあ $Y'$ を求めないといけない！になるのですが、 $\displaystyle Y'_{0} = 1, Y'_{i} = \sum_{j = \max(1, i - L - 1)}^{\min(i, D)} Y'_{j}$ で、計算式がまったく一緒。

dpの計算と同様、前からの和をよしなに変数で持っておけばこの計算も効率的にできる

実装

変数名等がこれまでの表記と噛み合ってないです。

int n, l, d;

void calcD(std::vector<long double>& D) {
    D[0] = 1.0;
    long double sum{};
    sum += D[0];
    for (int i{1} ; i < l + d ; i++) {
        D[i] = sum / (long double)d;
        if (i < l) sum += D[i];
        if (i - d >= 0) sum -= D[i - d];
    }
    for (int i{} ; i < l ; i++) D[i] = 0;
}

int main() {
    SetFastIO();

    std::cin >> n >> l >> d;
    std::vector<long double> D(std::max(n + 1, l + d));
    calcD(D);
    std::vector<long double> acm(D.size() + 1);
    for (int i{} ; i < (int)D.size() ; i++) {
        acm[i + 1] = acm[i] + D[i];
    }

    std::vector<long double> dp(n + 1);
    long double shake{};
    for (int i{n} ; i >= 0 ; i--) {
        long double here{
            acm.back() - acm[std::min((int)D.size(), n + 1)]
                +
            acm[std::min(i, (int)D.size())]
        };
        dp[i] = std::max(here, shake / (long double)d);
        shake += dp[i];
        if (i + d <= n) shake -= dp[i + d];
    }
    SetPrecision(-8);
    std::cout << dp[0] << '\n';
}

感想

累積和の添字が難しかったです。

全人類Gに突撃したのが原因なのか、自分が思っているよりdiffが高くでている。

人類クエリ処理が上手すぎるぜ

*1:明らかとかかっこつけて言っていますが、私はこれを忘れて2ペナしました....