結果

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

ソースコード

diff # 

#include <cassert>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <unordered_map>
#include <vector>

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

std::int64_t MyHash(const int x, const int y, const int z, const int n) {
  return (std::int64_t{x} * n + y) * n + z;
}

// プレイヤー player の操作前を考える。
// stay グループにいるプレイヤーの中で最も順位の低いプレイヤーの順位の期待値
mint StayPlayer(
    const int player, const int stay, const int bottom, const int n) {
  if (player == n) return n - bottom;
  static std::unordered_map<std::int64_t, mint> memo;
  const std::uint64_t key = MyHash(player, stay, bottom, n);
  if (const auto it = memo.find(key); it != memo.end()) return it->second;
  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 memo[key] = ans_0;
  // プレイヤー player は操作を行わない方が最適
  if (stay > bottom) return memo[key] = ans_1;
  return memo[key] = (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;
  static std::unordered_map<std::int64_t, mint> memo;
  if (player == n + 1) {
    std::cout << memo.size() << '\n';
    exit(0);
  }
  const std::uint64_t key = MyHash(player, stay, bottom, n);
  if (const auto it = memo.find(key); it != memo.end()) return it->second;
  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 memo[key] = ans_0;
  // プレイヤー player は操作を行った方が最適
  if (stay > bottom) return memo[key] = ans_1;
  return memo[key] = (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::unordered_map<int, mint> dp{{0, mint::raw(1)}};
  for (int player = 0; player < n; ++player) {
    mint ans = 0;
    std::unordered_map<int, mint> nxt;
    for (const auto& [key, prob] : dp) {
      if (prob == 0) continue;
      const int stay = key / n, behind = key % n;
      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) * n + behind] += prob;
      } else if (stay > behind) {
        ans += rank_1 * prob;
        nxt[stay * n + behind] += prob / 2;
        nxt[stay * n + behind + 1] += prob / 2;
      } else {
        assert(rank_0 == rank_1);
        ans += rank_0 * prob;  // どちらでもよい
        nxt[(stay + 1) * n + behind] += prob / 2;
        nxt[stay * n + behind] += prob / 4;
        nxt[stay * n + behind + 1] += prob / 4;
      }
    }
    dp.swap(nxt);
    std::cout << ans.val() << " \n"[player + 1 == n];
  }
  return 0;
}
0