結果

問題 No.3174 勝ち残りじゃんけん
コンテスト
ユーザー t98slider
提出日時 2025-03-02 11:07:47
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
RE  
実行時間 -
コード長 2,473 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,251 ms
コンパイル使用メモリ 255,172 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-03-02 11:07:54
合計ジャッジ時間 5,819 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;

    // Nが大きいケースは打ち切り
    assert(N <= 500);

    // 二項係数を計算
    vector<vector<mint>> binom(N + 1, vector<mint>(N + 1));
    binom[0][0] = 1;
    for(int i = 1; i <= N; i++){
        binom[i][0] = 1;
        for(int j = 1; j <= i; j++){
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }

    // 答え
    vector<mint> ans(N + 1);
    // i人以下になるまでの期待値を計算
    for(int i = 1; i <= N; i++){
        // dp[j] : j人の状態からi人以下になるまでの期待値
        vector<mint> dp(N + 1);
        // ちょうどj人の時の期待値を計算
        // i人以下になるまでの期待値を計算するのでi人以下は期待値0
        for(int j = i + 1; j <= N; j++){
            // j人でじゃんけんしたときのあいこの確率
            // 高校数学の美しい物語 (https://manabitimes.jp/math/1172)
            mint p_draw = 1 - ((mint(2).pow(j) - 2) / mint(3).pow(j - 1));
            // あいこではない確率
            mint not_draw;
            for(int k = 1; k < j; k++){
                // j人の中から残るk人を選ぶ
                // 勝ちの手の3通り (グー,チョキ), (チョキ,パー), (パー,グー)
                not_draw += 3 * binom[j][k];
            }
            // j人でじゃんけんをしたときの場合の数は 3**j 通り
            not_draw /= mint(3).pow(j);

            // あいこの確率とあいこではない確率が1に一致することを確認
            assert((p_draw + not_draw).val() == 1);

            // 1人 ~ j-1人 までの(期待値)×(確率)の積を計算
            not_draw = 0;
            for(int k = 1; k < j; k++){
                not_draw += 3 * binom[j][k];
                dp[j] += 3 * binom[j][k] * dp[k];
            }
            // あいこではない場合の総数から割る
            dp[j] /= not_draw;

            // j人を抜け出すまでに増える期待値 (あいこではない確率の逆数)
            dp[j] += 1 / (1 - p_draw);
        }
        // 答えを格納
        ans[i] = dp[N];
    }

    for(int i = 1; i <= N; i++){
        cout << ans[i].val() << (i == N ? '\n' : ' ');
    }
}
0