結果

問題 No.3055 Simple Chicken Game
ユーザー suisen
提出日時 2025-01-26 20:09:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,491 ms / 2,000 ms
コード長 4,984 bytes
コンパイル時間 1,489 ms
コンパイル使用メモリ 88,664 KB
実行使用メモリ 250,240 KB
最終ジャッジ日時 2025-02-05 00:30:02
合計ジャッジ時間 9,874 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#include <atcoder/modint>

// https://yukicoder.me/submissions/1039331 から以下を改善した
// dp_noop, dp_flip の k を 1 次元目に移動
int main() {
    using mint = atcoder::modint;
    constexpr int kMaxN = 3000, kMinP = 100000000, kMaxP = 1000000000;

    int n, p;
    std::cin >> n >> p;
    assert(1 <= n && n <= kMaxN);
    assert(kMinP <= p && p <= kMaxP);
    mint::set_mod(p);

    const mint inv2 = mint(2).inv(), inv4 = inv2 * inv2;

    // dp[k][i][j] は以下を前提とする
    // - i: これまで操作しなかったプレイヤーの人数
    // - j: まだ操作していないプレイヤーの人数
    // - これまでに操作した裏が出たプレイヤーの人数が i - 1 + k 人
    // dp_noop := 操作しなかったプレイヤーのうち、
    //            現時点で最下位のプレイヤーにおける最終的な順位の期待値
    // dp_flip := 操作して裏が出たプレイヤーのうち……
    std::vector dp_noop(3, std::vector(n + 1, std::vector(n + 1, mint())));
    std::vector dp_flip(3, std::vector(n + 1, std::vector(n + 1, mint())));
    for (int yet = 0; yet <= n; ++yet) {
        for (int noop = 0; noop + yet <= n; ++noop) {
            for (int k = std::max(-noop, -1); k <= 1; ++k) {
                const int flip = noop + k;
                if (noop + yet + flip > n) continue;
                if (yet == 0) {
                    dp_noop[k + 1][noop][yet] = noop;
                    dp_flip[k + 1][noop][yet] = noop + flip;
                    continue;
                }
                // 次のプレイヤーの選択を考える
                if (noop < flip) {  // 操作しない
                    dp_noop[k + 1][noop][yet] = dp_noop[k][noop + 1][yet - 1] - 1;
                    dp_flip[k + 1][noop][yet] = dp_flip[k][noop + 1][yet - 1];
                } else if (noop > flip) {  // 操作する
                    // 表
                    dp_noop[k + 1][noop][yet] += (dp_noop[k + 1][noop][yet - 1] + 1) * inv2;
                    dp_flip[k + 1][noop][yet] += (dp_flip[k + 1][noop][yet - 1] + 1) * inv2;
                    // 裏
                    dp_noop[k + 1][noop][yet] += dp_noop[k + 2][noop][yet - 1] * inv2;
                    dp_flip[k + 1][noop][yet] += (dp_flip[k + 2][noop][yet - 1] - 1) * inv2;
                } else {  // どちらでもよい
                    dp_noop[k + 1][noop][yet] += (dp_noop[k][noop + 1][yet - 1] - 1) * inv2;
                    dp_noop[k + 1][noop][yet] += (dp_noop[k + 1][noop][yet - 1] + 1) * inv4;
                    dp_noop[k + 1][noop][yet] += dp_noop[k + 2][noop][yet - 1] * inv4;
                    dp_flip[k + 1][noop][yet] += dp_flip[k][noop + 1][yet - 1] * inv2;
                    dp_flip[k + 1][noop][yet] += (dp_flip[k + 1][noop][yet - 1] + 1) * inv4;
                    dp_flip[k + 1][noop][yet] += (dp_flip[k + 2][noop][yet - 1] - 1) * inv4;
                }
            }
        }
    }

    // dp[i][k] := これまで最適な操作がなされてきたときに以下を満たす確率
    // - 操作しなかったプレイヤーが i 人
    // - 操作して裏が出たプレイヤーの人数が i - 1 + k 人
    std::vector dp(1, std::vector(3, mint()));
    dp[0][0 + 1] = 1;
    for (int player = 0; player < n; ++player) {
        std::vector nxt(player + 2, std::vector(3, mint()));
        mint ans = 0;
        const int yet = n - 1 - player;
        for (int noop = 0; noop <= player; ++noop) {
            for (int k = std::max(-noop, -1); k <= 1; ++k) {
                const int flip = noop + k;
                if (noop + flip > player) break;
                const int tip = player - (noop + flip);  // 表を出したプレイヤーの人数
                const mint prob = dp[noop][k + 1];
                // 現在のプレイヤーの選択を考える
                if (noop < flip) {  // 操作しない
                    ans += (tip + dp_noop[k][noop + 1][yet]) * prob;
                    nxt[noop + 1][k] += prob;
                } else if (noop > flip) {  // 操作する
                    // 表
                    ans += (tip + 1) * prob * inv2;
                    nxt[noop][k + 1] += prob * inv2;
                    // 裏
                    ans += (tip + dp_flip[k + 2][noop][yet]) * prob * inv2;
                    nxt[noop][k + 2] += prob * inv2;
                } else {  // どちらでもよい
                    assert(dp_noop[k][noop + 1][yet] == (1 + dp_flip[k + 2][noop][yet]) * inv2);
                    ans += (tip + dp_noop[k][noop + 1][yet]) * prob;
                    nxt[noop + 1][k] += prob * inv2;
                    nxt[noop][k + 1] += prob * inv4;
                    nxt[noop][k + 2] += prob * inv4;
                }
            }
        }
        dp.swap(nxt);
        std::cout << ans.val() << " \n"[player + 1 == n];
    }
    return 0;
}
0