目次
AtCoder Beginner Contest 149 D～F問題メモ
D - Prediction and Restriction
問題
- じゃんけんマシンと $N$ 回対戦する
- じゃんけんマシンの各回で出す手は決まっていて、文字列 $S$ で与えられる
- グーで勝つと $R$ 点、チョキで勝つと $S$ 点、パーで勝つと $P$ 点もらえる。あいこと負けは0点
- 各対戦で、$K$ 回前に出した手と同じ手を出すことは禁止されている。最初の $K$ 回は好きに出してよい
- 得点を最大化せよ
- $2 \le N \le 10^5$
解法
貪欲に勝てる手を出していく。
$K$ 回前の禁止ルールに引っかかり勝てる手を出せない場合のみ、仕方ないので違う手を出す。
この時、2通りの出し方があるので、さらに $K$ 回後の勝利を邪魔しないような手を選ぶことができる。
K回前,今,K回後が同じ場合
|<-- K回 --|-- K回 -->|
マシン パ パ パ
挑戦者 チ グorパ チ
↑
K回前と異なる2つの手のどちらを出してもK回後に勝てる手を出せる
K回前,今が同じで、K回後が異なる場合
|<-- K回 --|-- K回 -->|
マシン パ パ チ
挑戦者 チ パ グ
↑
K回前と異なり、かつK回後に勝つための手も邪魔しない手を選べる
- じゃんけんマシンの $K$ 回前が違う手の場合、勝てる手の得点を加算
- じゃんけんマシンの $K$ 回前が同じ手で、その時に得点を得ている場合は、禁止ルールで0点
- じゃんけんマシンの $K$ 回前が同じ手で、その時に0点の場合は、勝てる手の得点を加算
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
ans = [0] * n
for i, c in enumerate(t):
if i >= k and c == t[i - k] and ans[i - k] > 0:
continue
if c == 'r':
ans[i] = p
elif c == 's':
ans[i] = r
else:
ans[i] = s
print(sum(ans))
E - Handshake
問題
- 長さ $N$ の数列 $A_1,A_2,...,A_N$ が与えられる
- ここから2要素の組 $(A_i,A_j)$（$i=j$ でもよい、順番も区別する）の選び方は $N^2$ 通りある
- 2要素の和が大きい方から順に $M$ 組を取った時、$M$ 組の和の合計を求めよ
- $1 \le N \le 10^5$
- $1 \le M \le N^2$
- $1 \le A_i \le 10^5$
解法
実際に全組の和を作ると $N^2$ 個できてえらいことになるので、何かしらまとめることを考える。
「和が $X$ 以上になる組が $M$ 個以上できるか？」を $X$ を固定して考えると、 これは $X$ が小さいほど少なく大きいほど多くなるので、二分探索でちょうど $M$ 個以上作れる境界を探せる。
境界が分かれば、そのような組だけ抽出して和の合計を計算することができる。
$X$ を探す範囲は 2～$A_i$ の最大値x2、1回の判定が $O(N \log{N})$、最後の和の合計の算出も $O(N \log{N})$ より、全部で $O(N \log{N} \log{A_{max}})$ でできる。
(例) X=10 で M=8 個以上できるか？
Ai
12 [12,8,3,1] 相方は4個全て可能
8 [12,8,3] 相方は3通り
3 [12,8] 相方は2通り
1 [12] 相方は1通り
→計 10組の合計が 10以上になる
注意すべきは、$M$ 個以上作れる境界が $X$ であっても、同率があるため和が $X$ である組全てを採用できるわけでは無いこと。
M = 4
組の和(降順) 10, 9, 9, 8, 8, 8, 7, ...
~~~~~~~~~~~~
X=8だが、そのうち採用できるのは1個
よって $X$ を求めた後、和の合計を求める段階では、 まず「和が $X+1$ 以上である組の数」を求めた上で、$M$ に足りない分だけ和が $X$ の組を採用すればよい。
from bisect import bisect, bisect_left
from itertools import accumulate
def check(x):
count = 0
for a in aaa:
if x <= a:
count += n
else:
count += n - bisect_left(aaa, x - a)
return count >= m
n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
acc = [0] + list(accumulate(aaa))
sum_a = acc[-1]
l, r = 0, 200001
while l + 1 < r:
mid = (l + r) // 2
if check(mid):
l = mid
else:
r = mid
# 合計がlより大きい組み合わせの和と組数を求める→Mに足りない分だけ合計がlの組を採用
ans = 0
count = 0
for a in aaa:
if l <= a:
ans += sum_a + a * n
count += n
else:
omit = bisect(aaa, l - a)
if omit < n:
ans += sum_a - acc[omit] + a * (n - omit)
count += n - omit
ans += l * (m - count)
print(ans)
F - Surrounded Nodes
問題
- $N$ 頂点の木があり、構造も与えられる
- 各頂点を $\frac{1}{2}$ ずつの確率で白か黒に塗る
- 黒く塗られた頂点を全て含むような最小の全域木を $S$ とする
- $S$ の中に含まれる白い頂点の個数の期待値を求めよ
- $2 \le N \le 2 \times 10^5$
解法
「$S$ に含まれる白い頂点の個数の期待値」は、切り口を変えて「自分が『$S$ に含まれる白い頂点』となる確率」を全頂点について求め、合計したものに等しくなる。 和の期待値＝期待値の和。
条件
どのような頂点が「$S$ に含まれる白い頂点」となるか？
- 自身が白いこと
- 子の部分木のうち、黒い頂点が1つでも含まれるものが、2つ以上あること
2番目の条件については、自身が $S$ に含まれるための条件となる。
子1 自 子3
○ -- ○ -- ○ -- ● -- ○ -- ●
｜
子2○ -- ○
子1～3の部分木のうち、黒い頂点を含むものが1個しか無い場合、$S$ はその部分木の中だけで完結してしまうので、自身は $S$ に含まれない。
一方、2個以上あれば、その黒い頂点同士を結ぶ過程で必ず自身も $S$ に含まれる。
確率
次に、その時の確率を考える。
長いので、説明上「黒い頂点が1つでも含まれる部分木」を「$B$」と表す。
「子の部分木の内、$B$ が2つ以上含まれる確率」は、余事象「$B$ が1つ以下しかない確率」の方が計算しやすいので、これを1から引くことで求める。
ある $k$ 個の頂点について、そいつらが全て白である確率は $\displaystyle \frac{1}{2^k}$、 1つでも黒が含まれる確率は $\displaystyle 1-\frac{1}{2^k}$ となる。
よって、たとえば子1～3の頂点数が $k_1,k_2,k_3$ 個なら、以下の合計となる。
- $B$ が0個…$\displaystyle \frac{1}{2^{k_1+k_2+k_3}}$
- $B$ が1個
- 子1が $B$ … $\displaystyle (1-\frac{1}{2^{k_1}})\frac{1}{2^{k_2+k_3}}$
- 子2が $B$ … $\displaystyle (1-\frac{1}{2^{k_2}})\frac{1}{2^{k_1+k_3}}$
- 子3が $B$ … $\displaystyle (1-\frac{1}{2^{k_3}})\frac{1}{2^{k_1+k_2}}$
この合計は、以下のように変形できる。
- $\displaystyle \frac{1}{2^{k_2+k_3}} + \frac{1}{2^{k_1+k_3}} + \frac{1}{2^{k_1+k_2}} - (3-1)\frac{1}{2^{k_1+k_2+k_3}} $
これを計算して余事象をとり、自身が白である確率1/2をかけたものが、求めるべき「自分が『$S$ に含まれる白い頂点』となる確率」である。
全方位DP
ある頂点について確率を求めるには、自身から伸びる全方向の部分木の頂点数が必要となる。
しかし、たとえばある頂点を根として探索したとして、1回の探索だけでは「親方向の部分木の情報」がわからない。
根(仮)
／ ＼ ←こっち方面の頂点数はわからない
○ ●
/ /\ ←DFSなどで、各子の部分木の頂点数は求められる
??? ○○
｜
○
そこで、1回まずDFSで子方向の部分木の情報だけ計算しておいて、2回目で親方向の部分木の情報を与えながら探索すると可能となる。
必要なのは頂点数だけなので、全体 $N$ から自分+子の頂点数の総計を引けば求まるね。
実装の方法
今回の制約では再帰数が $2 \times 10^5$ 近くまであり得るが、DFSを再帰関数で書くと、ほぼ直線のような木の場合にTLEする。 スタックに積んでいく実装では間に合った。
「子の探索が終了した後、それを合計するなど集約して、自身の情報とする」ような探索の場合、再帰の方が書きやすいのだが、なかなか無視できない差が生じる。
import sys
def dfs1(root, links):
""" まず、適当に根を定め、各ノードの親と、子毎の部分木のサイズを計算しておく """
parent = [0] * n
subtree_count = [{} for _ in range(n)]
q = [(root, -1, 0)] # (v, p, t) p:親ノード番号 t:0=初来訪, 1=全ての子巡回後
while q:
v, p, t = q.pop()
if t == 0:
parent[v] = p
q.append((v, p, 1))
for u in links[v]:
if u == p:
continue
q.append((u, v, 0))
elif p != -1:
subtree_count[p][v] = sum(subtree_count[v].values()) + 1
return parent, subtree_count
def dfs2(root, parent, subtree_count, d2, d2s):
"""
各ノードにつき「自身から伸びる部分木のうち、黒が1つでもある枝が2本以上ある確率」を足していく
"""
ans = 0
q = [(root, 0)] # (v, pc) pc:vから見て親方面の部分木のノード数
while q:
v, pc = q.pop()
if len(subtree_count[v]) == 0:
continue
p = parent[v]
children, st_counts = map(list, zip(*subtree_count[v].items()))
children.append(p)
st_counts.append(pc)
cl = len(st_counts)
ct = sum(st_counts)
for u, stc in subtree_count[v].items():
q.append((u, ct - stc + 1))
if cl == 1:
continue
tmp = 0
for stc in st_counts:
tmp = (tmp + d2s[ct - stc]) % MOD
tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
ans = (ans + (1 - tmp) * d2) % MOD
return ans
n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
a, b = map(int, line.split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
root = 0
MOD = 10 ** 9 + 7
d2 = 500000004 # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
d2s.append(d2s[-1] * d2 % MOD)
parent, subtree_count = dfs1(root, links)
ans = dfs2(root, parent, subtree_count, d2, d2s)
print(ans)
