−目次

AtCoder Beginner Contest 149 D～F問題メモ

AtCoder Beginner Contest 149 D～F問題メモ

AtCoder Beginner Contest 149

今年も終わり。

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)

            

        
      