提出 #44543877

ソースコード 拡げる

# 解説 https://atcoder.jp/contests/abc314/editorial/6978 の実装例

n = int(input())
C = [list(map(int, input().split())) for _ in range(n - 1)]
mod = 998244353

# 0-indexed に直す
for i in range(n - 1):
    for j in range(2):
        C[i][j] -= 1


def inv(x):
    """x の mod での逆元を返す。mod が素数で、x と mod が互いに素である必要あり。"""
    x %= mod
    return pow(x, mod - 2, mod)


# マージテク操作 1 回目

team = [[i] for i in range(n)]  # チーム一覧
blng = [i for i in range(n)]  # プレイヤー i は現在チーム U[i] に所属している

for i in range(n - 1):
    a, b = C[i][0], C[i][1]
    n_team_a = len(team[blng[a]])  # a が属するチームの人数
    n_team_b = len(team[blng[b]])  # b が属するチームの人数
    if n_team_a < n_team_b:
        a, b = b, a
    team[blng[a]] += team[blng[b]]
    for j in team[blng[b]]:  # 所属変更
        blng[j] = blng[a]

# 数列 A を求める
for i in range(n):
    if len(team[i]) == n:
        A = team[i]

# 番号振り直し
no_new = [-1] * n
for i in range(n):
    no_new[A[i]] = i

for i in range(n - 1):
    for j in range(2):
        C[i][j] = no_new[C[i][j]]


# マージテク操作 2 回目 (期待値の数列の構築もする)

e_imos = [0] * (n + 1)  # 期待値の数列

team = [[i] for i in range(n)]  # チーム一覧
blng = [i for i in range(n)]  # プレイヤー i は現在チーム U[i] に所属している

for i in range(n - 1):
    a, b = C[i][0], C[i][1]
    n_team_a = len(team[blng[a]])  # a が属するチームの人数
    n_team_b = len(team[blng[b]])  # b が属するチームの人数

    min_mem_a = team[blng[a]][0]  # a が属するチームの番号最小のプレイヤー
    min_mem_b = team[blng[b]][0]  # b が属するチームの番号最小のプレイヤー
    win_rate_a = (n_team_a * inv(n_team_a + n_team_b)) % mod
    win_rate_b = (n_team_b * inv(n_team_a + n_team_b)) % mod

    e_imos[min_mem_a] += win_rate_a
    e_imos[min_mem_a] %= mod
    e_imos[min_mem_a + n_team_a] -= win_rate_a
    e_imos[min_mem_a + n_team_a] %= mod

    e_imos[min_mem_b] += win_rate_b
    e_imos[min_mem_b] %= mod
    e_imos[min_mem_b + n_team_b] -= win_rate_b
    e_imos[min_mem_b + n_team_b] %= mod

    if n_team_a < n_team_b:
        a, b = b, a
    team[blng[a]] += team[blng[b]]
    for j in team[blng[b]]:  # 所属変更
        blng[j] = blng[a]

# 累積和をとる
for i in range(1, n + 1):
    e_imos[i] += e_imos[i - 1]
    e_imos[i] %= mod

# 振り直す前の番号を考慮した解答を作成
ANS = [-1] * n
for i in range(n):
    ANS[A[i]] = e_imos[i]

print(*ANS)

提出情報

提出日時
問題 F - A Certain Game
ユーザ Tomii9273
言語 Python (PyPy 3.10-v7.3.12)
得点 475
コード長 2757 Byte
結果 AC
実行時間 549 ms
メモリ 195436 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 475 / 475
結果
AC × 2
AC × 41
セット名 テストケース
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, example0.txt, example1.txt
ケース名 結果 実行時間 メモリ
000.txt AC 56 ms 76528 KiB
001.txt AC 467 ms 195116 KiB
002.txt AC 464 ms 195436 KiB
003.txt AC 467 ms 195280 KiB
004.txt AC 427 ms 169668 KiB
005.txt AC 421 ms 169824 KiB
006.txt AC 429 ms 169672 KiB
007.txt AC 244 ms 117956 KiB
008.txt AC 314 ms 136840 KiB
009.txt AC 205 ms 109576 KiB
010.txt AC 507 ms 182576 KiB
011.txt AC 390 ms 154160 KiB
012.txt AC 499 ms 181368 KiB
013.txt AC 417 ms 162328 KiB
014.txt AC 255 ms 122612 KiB
015.txt AC 181 ms 102732 KiB
016.txt AC 416 ms 163120 KiB
017.txt AC 517 ms 186788 KiB
018.txt AC 549 ms 186516 KiB
019.txt AC 513 ms 186024 KiB
020.txt AC 534 ms 186940 KiB
021.txt AC 512 ms 185124 KiB
022.txt AC 520 ms 186604 KiB
023.txt AC 520 ms 187112 KiB
024.txt AC 521 ms 186012 KiB
025.txt AC 532 ms 186872 KiB
026.txt AC 515 ms 185984 KiB
027.txt AC 520 ms 186228 KiB
028.txt AC 528 ms 186484 KiB
029.txt AC 513 ms 186160 KiB
030.txt AC 528 ms 187408 KiB
031.txt AC 514 ms 186920 KiB
032.txt AC 518 ms 185436 KiB
033.txt AC 524 ms 187236 KiB
034.txt AC 530 ms 186184 KiB
035.txt AC 522 ms 187084 KiB
036.txt AC 516 ms 187216 KiB
037.txt AC 370 ms 169008 KiB
038.txt AC 376 ms 168712 KiB
example0.txt AC 56 ms 76480 KiB
example1.txt AC 56 ms 76556 KiB