AtCoder ABC160 参加メモ

全完できて黄色パフォでした！嬉しい！

全方位木をあまり理解していなかったためFが遅くなってしまいましたが、方針自体はすぐたったのでまだ上を目指せそうです。

E Red and Green Apples

貪欲で解けます。 時間がかかった人も割といたようですが早く解けました。 いつもは貪欲に気づくの苦手の部類なんですが... Pの上位A個分、Qの上位B個分を連結しソートします。Rもソートしておいて、max(R) > min(P+Q)だったら入れ替えるのを繰り返して解きました。

F Distributing Integers

全方位木です。以前EDPCで出たのをよくわからず通したままになっていたので復習しないとなあと思っていたのですが、出てしまい困ってしまいました。 atcoder.jp

本番ではEDPCの解説記事を読みながらゆっくり書いてギリギリACできました。

たくさんの方が解説ブログを挙げています。以下を参考にすればよくわかりそうです。

AtCoder Beginner Contest 160 F - Distributing Integers - ARMERIA

AtCoder Beginner Contest 160 解法 - ブログ名

ここではpythonで書いた自分のコードを整理してコメントをつけたのを公開しておきます。 pythonでは再帰がとても重いので非再帰で解いています。

import sys;input=sys.stdin.readline

mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, 2*10**5 + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# ここまでライブラリ

N, = map(int, input().split())
d = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)


# 予めノードをdfs順に保持
vs = set([1])
stack = [1]
vs_dfs = list()
parents = [0] * (N+1)
while stack:
    v = stack.pop()
    vs_dfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        stack.append(u)

# 根を1として計算、同時に部分木のサイズも計算しておく
dp1 = [0 for _ in range(N+1)]
size = [0 for _ in range(N+1)]
for v in vs_dfs[::-1]:
    t = 1
    tmp = 0
    for u in d[v]:
        if u == parents[v]:
            continue
        t = mul(dp1[u], t)
        tmp += size[u]
        t = mul(t, cmb(tmp, size[u]))
    size[v] = tmp + 1
    dp1[v] = t

# v=1以外を根にして計算
for v in vs_dfs[1:]:
    p = parents[v]
    dp1[v] = mul(
            mul(dp1[p], size[v]),
            inverse[N-size[v]]
            )
for i in range(1, N+1):
    print(dp1[i])