結果

問題 No.3055 Simple Chicken Game
コンテスト
ユーザー emthrm
提出日時 2025-01-25 18:08:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,280 bytes
コンパイル時間 3,767 ms
コンパイル使用メモリ 123,244 KB
実行使用メモリ 14,848 KB
最終ジャッジ日時 2025-02-05 00:28:47
合計ジャッジ時間 68,257 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <compare>
#include <iostream>
#include <limits>
#include <numeric>
#include <tuple>
#include <vector>

#include <atcoder/modint>

namespace emthrm {

template <typename T = long long>
struct Rational {
  T num, den;

  Rational() : num(0), den(1) {}
  Rational(const T num, const T den = 1) : num(num), den(den) {
    // assert(den != 0);
    reduce();
  }

  template <typename Real = long double>
  Real to_real() const { return static_cast<Real>(num) / den; }

  Rational& operator+=(const Rational& x) {
    const T g = std::gcd(den, x.den);
    num = num * (x.den / g) + x.num * (den / g);
    den *= x.den / g;
    reduce();
    return *this;
  }
  Rational& operator-=(const Rational& x) { return *this += -x; }

  Rational& operator*=(const Rational& x) {
    const T g1 = std::gcd(num, x.den), g2 = std::gcd(den, x.num);
    num = (num / g1) * (x.num / g2);
    den = (den / g2) * (x.den / g1);
    reduce();
    return *this;
  }
  Rational& operator/=(const Rational& x) {
    return *this *= Rational(x.den, x.num);
  }

  auto operator<=>(const Rational& x) const {
    return num * x.den <=> x.num * den;
  }
  bool operator==(const Rational& x) const {
    return num == x.num && den == x.den;
  }

  Rational& operator++() {
    if ((num += den) == 0) den = 1;
    return *this;
  }
  Rational operator++(int) {
    const Rational res = *this;
    ++*this;
    return res;
  }
  Rational& operator--() {
    if ((num -= den) == 0) den = 1;
    return *this;
  }
  Rational operator--(int) {
    const Rational res = *this;
    --*this;
    return res;
  }

  Rational operator+() const { return *this; }
  Rational operator-() const { return Rational(-num, den); }

  Rational operator+(const Rational& x) const { return Rational(*this) += x; }
  Rational operator-(const Rational& x) const { return Rational(*this) -= x; }
  Rational operator*(const Rational& x) const { return Rational(*this) *= x; }
  Rational operator/(const Rational& x) const { return Rational(*this) /= x; }

  friend std::ostream& operator<<(std::ostream& os, const Rational& x) {
    if (x.den == 1) return os << x.num;
    return os << x.num << '/' << x.den;
  }

 private:
  void reduce() {
    const T g = std::gcd(num, den);
    num /= g;
    den /= g;
    if (den < 0) {
      num = -num;
      den = -den;
    }
  }
};

}  // namespace emthrm

using rational = emthrm::Rational<>;

rational StayPlayer(const int, const int, const int, const int);
rational BottomPlayer(const int, const int, const int, const int);

// プレイヤー player の順位の期待値
std::tuple<rational, rational, rational> Calc(
    const int player, const int unreach, const int stay, const int n) {
  return {
    // 操作を行わなかったとき
    StayPlayer(player + 1, unreach, stay + 1, n),
    // 操作を行ったとき (1) 表
    unreach + 1,
    // 操作を行ったとき (2) 裏
    BottomPlayer(player + 1, unreach, stay, n),
  };
}

// プレイヤー player の操作前を考える。
// stay グループにいるプレイヤーの中で最も順位の低いプレイヤーの順位の期待値
rational StayPlayer(
    const int player, const int unreach, const int stay, const int n) {
  if (player == n) return unreach + stay;
  const auto [rank_0, rank_10, rank_11] = Calc(player, unreach, stay, n);
  // プレイヤー player は操作を行わない方が最適
  const rational ans_0 = rank_0 - 1;
  if (rank_0 < (rank_10 + rank_11) / 2) return ans_0;
  // プレイヤー player は操作を行った方が最適
  rational ans_1 = 0;
  ans_1 += StayPlayer(player + 1, unreach + 1, stay, n);  // 表
  ans_1 += StayPlayer(player + 1, unreach, stay, n);  // 裏
  ans_1 /= 2;
  if ((rank_10 + rank_11) / 2 < rank_0) return ans_1;
  // どちらでもよい
  return (ans_0 + ans_1) / 2;
}

// プレイヤー player の操作前を考える。
// bottom グループにいるプレイヤーの中で最も順位の低いプレイヤーの順位の期待値
rational BottomPlayer(
    const int player, const int unreach, const int stay, const int n) {
  if (player == n) return n;
  const auto [rank_0, rank_10, rank_11] = Calc(player, unreach, stay, n);
  // プレイヤー player は操作を行わない方が最適
  const rational ans_0 = BottomPlayer(player + 1, unreach, stay + 1, n);
  if (rank_0 < (rank_10 + rank_11) / 2) return ans_0;
  // プレイヤー player は操作を行った方が最適
  rational ans_1 = 0;
  ans_1 += BottomPlayer(player + 1, unreach + 1, stay, n);  // 表
  ans_1 += rank_11 - 1;  // 裏
  ans_1 /= 2;
  if ((rank_10 + rank_11) / 2 < rank_0) return ans_1;
  // どちらでもよい
  return (ans_0 + ans_1) / 2;
}

// 有理数を用いて愚直に計算する
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);

  std::vector dp(1, std::vector{rational(1)});
  for (int player = 0; player < n; ++player) {
    rational ans = 0;
    std::vector nxt(player + 2, std::vector(player + 2, rational(0)));
    // 上位が確定しているプレイヤー
    for (int in_front = 0; in_front <= player; ++in_front) {
      // 下位が確定しているプレイヤー
      for (int behind = 0; in_front + behind <= player; ++behind) {
        const rational prob = dp[in_front][behind];
        if (prob == 0) continue;
        const auto [rank_0, rank_10, rank_11] =
            Calc(player, in_front, player - (in_front + behind), n);
        if (rank_0 < (rank_10 + rank_11) / 2) {
          ans += rank_0 * prob;
          nxt[in_front][behind] += prob;
        } else if ((rank_10 + rank_11) / 2 < rank_0) {
          ans += (rank_10 + rank_11) / 2 * prob;
          nxt[in_front + 1][behind] += prob / 2;
          nxt[in_front][behind + 1] += prob / 2;
        } else {
          ans += rank_0 * prob;  // どちらでもよい
          nxt[in_front][behind] += prob / 2;
          nxt[in_front + 1][behind] += prob / 4;
          nxt[in_front][behind + 1] += prob / 4;
        }
      }
    }
    dp.swap(nxt);
    std::cout << (mint(ans.num) / ans.den).val() << " \n"[player + 1 == n];
  }
  return 0;
}
0