結果

問題 No.3055 Simple Chicken Game
ユーザー emthrm
提出日時 2025-01-25 19:08:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,761 bytes
コンパイル時間 1,971 ms
コンパイル使用メモリ 96,924 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-02-05 00:28:29
合計ジャッジ時間 44,116 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include <atcoder/modint>
using mint = atcoder::modint;

// プレイヤー player の操作前を考える。
// stay グループにいるプレイヤーの中で最も順位の低いプレイヤーの順位の期待値
mint StayPlayer(
    const int player, const int stay, const int bottom, const int n) {
  if (player == n) return n - bottom;
  mint ans_0 = 0, ans_1 = 0;  // どちらでもよいケースのためだけにメモしておく
  if (stay <= bottom) ans_0 = StayPlayer(player + 1, stay + 1, bottom, n) - 1;
  if (stay >= bottom) {
    ans_1 += StayPlayer(player + 1, stay, bottom, n);  // 表
    ans_1 += StayPlayer(player + 1, stay, bottom + 1, n);  // 裏
    ans_1 /= 2;
  }
  // プレイヤー player は操作を行った方が最適
  if (stay < bottom) return ans_0;
  // プレイヤー player は操作を行わない方が最適
  if (stay > bottom) return ans_1;
  return (ans_0 + ans_1) / 2;  // どちらでもよい
}

// プレイヤー player の操作前を考える。
// bottom グループにいるプレイヤーの中で最も順位の低いプレイヤーの順位の期待値
mint BottomPlayer(
    const int player, const int stay, const int bottom, const int n) {
  if (player == n) return n;
  mint ans_0 = 0, ans_1 = 0;  // どちらでもよいケースのためだけにメモしておく
  if (stay <= bottom) ans_0 = BottomPlayer(player + 1, stay + 1, bottom, n);
  if (stay >= bottom) {
    ans_1 += BottomPlayer(player + 1, stay, bottom, n);  // 表
    ans_1 += BottomPlayer(player + 1, stay, bottom + 1, n) - 1;  // 裏
    ans_1 /= 2;
  }
  // プレイヤー player は操作を行わない方が最適
  if (stay < bottom) return ans_0;
  // プレイヤー player は操作を行った方が最適
  if (stay > bottom) return ans_1;
  return (ans_0 + ans_1) / 2;  // どちらでもよい
}

// プレイヤーの最適手は以下のみに依存することを前提としている。
// - 以前に操作を行わなかったプレイヤーの人数
// - 以前に操作を行って裏が出たプレイヤーの人数
int main() {
  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);

  std::vector dp(1, std::vector{mint::raw(1)});
  for (int player = 0; player < n; ++player) {
    mint ans = 0;
    std::vector nxt(player + 2, std::vector(player + 2, mint()));
    // 操作しなかったプレイヤー
    for (int stay = 0; stay <= player; ++stay) {
      // 下位が確定しているプレイヤー
      for (int behind = 0; stay + behind <= player; ++behind) {
        const mint prob = dp[stay][behind];
        if (prob == 0) continue;
        mint rank_0 = 0, rank_1 = 0;
        if (stay <= behind) {
          rank_0 = StayPlayer(player + 1, stay + 1, behind, n);
        }
        if (stay >= behind) {
          rank_1 += player - (stay + behind) + 1;  // 表
          rank_1 += BottomPlayer(player + 1, stay, behind + 1, n);  // 裏
          rank_1 /= 2;
        }
        if (stay < behind) {
          ans += rank_0 * prob;
          nxt[stay + 1][behind] += prob;
        } else if (stay > behind) {
          ans += rank_1 * prob;
          nxt[stay][behind] += prob / 2;
          nxt[stay][behind + 1] += prob / 2;
        } else {
          assert(rank_0 == rank_1);
          ans += rank_0 * prob;  // どちらでもよい
          nxt[stay + 1][behind] += prob / 2;
          nxt[stay][behind] += prob / 4;
          nxt[stay][behind + 1] += prob / 4;
        }
      }
    }
    dp.swap(nxt);
    std::cout << ans.val() << " \n"[player + 1 == n];
  }
  return 0;
}
0