結果

問題 No.3055 Simple Chicken Game
コンテスト
ユーザー emthrm
提出日時 2025-01-26 19:57:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 804 ms / 2,000 ms
コード長 4,484 bytes
コンパイル時間 1,978 ms
コンパイル使用メモリ 110,948 KB
実行使用メモリ 214,912 KB
最終ジャッジ日時 2025-02-05 00:29:52
合計ジャッジ時間 7,256 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include <atcoder/modint>

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

  // dp[i][k] := これまで最適な操作がなされてきたときに以下を満たす確率
  // - 操作しなかったプレイヤーが i 人
  // - 操作して裏が出たプレイヤーの人数が i - 1 + k 人
  std::vector dp(1, std::array<mint, 3>{});
  dp[0][0 + 1] = 1;
  for (int player = 0; player < n; ++player) {
    std::vector nxt(player + 2, std::array<mint, 3>{});
    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[noop + 1][yet][k]) * 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[noop][yet][k + 2]) * prob * inv2;
          nxt[noop][k + 2] += prob * inv2;
        } else {  // どちらでもよい
          assert(dp_noop[noop + 1][yet][k] == (1 + dp_flip[noop][yet][k + 2]) * inv2);
          ans += (tip + dp_noop[noop + 1][yet][k]) * 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