AtCoder Beginner Contest 447 E,F,G問題メモ

AtCoder Beginner Contest 447

E - Divide Graph

• $N$ 頂点 $M$ 辺からなる単純連結無向グラフ $G$ が与えられます。
• 各辺には コスト とよばれる値が定められており、辺 $i$ のコストは $2^i$ です。
• あなたは今から、$G$ の連結成分の個数がちょうど $2$ になるように、$G$ の辺のうちいくつかを選んで削除します。
• 削除する辺のコストの和としてありうる最小値を $998244353$ で割った余りを求めてください。
  • $998244353$ で割った余りを最小化するのではないことに注意してください。

• $2\leq N \leq 2\times 10^5$
• $N-1\leq M \leq \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)$
• $1\leq U_i \lt V_i \leq N$
• $i\neq j$ ならば $(U_i, V_i) \neq (U_j, V_j)$
• $G$ は連結
• 入力は全て整数

コストが特殊で、辺 $i$ を消すより、$1～i-1$ の全てを消す方が必ず安い。
「辺 $i$ を残すことで、辺 $i-1,i-2,...$ など複数の辺を消さなければならない」ことになったとしても、 辺 $i$ の1本を消さずに残す方がよいということである。

よって、$i$ が大きい方から、残せる限り（残したら連結成分が1つになってしまわない限り）貪欲に残すのがよい。

DSU等を用いて、バラバラの $N$ 頂点をマージしていくことを考える。

$i$ が大きい辺から、連結成分が2個になるまで（$N-2$ 回、異なる連結成分をマージするまで）マージしていく。
それまでの辺は全て残せる。

それより小さい $i$ については、既に同じ連結成分に含まれる2頂点を結ぶものなら、残してよい。
残された2個の連結成分を結ぶものであれば消す必要があるので、$2^i$ をコストに加算する。

Python3

from atcoder.dsu import DSU


def solve(n, m, edges):
    MOD = 998244353
    uft = DSU(n)
    merged_count = 0
    ans = 0
    i = m - 1
    while merged_count < n - 2:
        u, v = edges[i]
        u -= 1
        v -= 1
        if not uft.same(u, v):
            merged_count += 1
        uft.merge(u, v)
        i -= 1
    for j in range(i, -1, -1):
        u, v = edges[j]
        u -= 1
        v -= 1
        if uft.same(u, v):
            continue
        ans += pow(2, j + 1, MOD)

    ans %= MOD
    return ans


n, m = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print(ans)

F - Centipede Graph

• 頂点に $1$ から $N$ の番号がついた $N$ 頂点の木 $T$ が与えられます。
• 正整数 $k$ について「長さ $k$ のムカデグラフ」を以下の手順で得られる頂点数 $3k$ のグラフと定義します。
  • 頂点数 $k$ のパスグラフを用意する。
  • そのパスグラフの各頂点 $v$ に対して、$v$ のみに隣接する $2$ つの頂点を新たに追加する。
• 例えば、長さ $4$ のムカデグラフは下図のようになります。

  • ○  ○  ○  ○
    │  │  │  │
    ○─○─○─○
    │  │  │  │
    ○  ○  ○  ○

• 木 $T$ の部分グラフとして含まれる「長さ $x$ のムカデグラフ」のうち、最大の $x$ を求めて下さい。
• $Q$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \le Q$
• $3 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• 与えられるグラフは木
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

$N \ge 3$ より、長さ $1$ のムカデグラフは必ず作れる。（これがコーナーで、気付くのに時間かかった）

○--○--○    ←N >= 3 ならこの部分グラフは必ず含まれる

長さ $2$ 以上を考える。
長さ $2$ 以上のパスグラフに対して、 そこに足を生やしたムカデグラフが木に含まれるかどうかは、頂点の次数で判定できる。
パスグラフの各頂点の次数を順に並べたものが $(3以上,4以上,4以上,...,4以上,3以上)$ ならよい。

木から、次数がこのようになる最長のパスグラフを見つければよい。

以下、単に「パスグラフ」と言ったとき、次数の条件を満たすもののみを指すとする。

適当な頂点を根として、木DPをおこなう。

• $\mathrm{DP}[v]:=v$ から親に向かう辺で、継続中の最長のパスグラフの長さ

また、$Ans=1$ で初期化し、木DPの途中で確定したものでMaxを更新していく。

頂点 $v$ の次数を $d_v$、頂点 $v$ の子の集合を $C_v$ で表す。

$d_v \lt 3$ の時、$v$ がパスグラフの一員となることはない。$\mathrm{DP}[v]=0$ である。

$d_v = 3$ の時、

• $v$ で終わるパスグラフが確定できる。$\max_{u \in C_v}\mathrm{DP}[u]+1$ で $Ans$ を更新する。
• $v$ からパスグラフを開始できる。$\mathrm{DP}[v]=1$ とする。

$d_v \ge 4$ の時、

• $v$ を中継点として、2つの子のパスグラフをマージし、確定できる。
  • $\{u \in C_v|\mathrm{DP}[u]\}$ の上位2つを $x,y$ として、$x+y+1$ で $Ans$ を更新する。
• 1つの子から続くパスグラフを親に継承できる。
  • $\mathrm{DP}[v]=\max_{u \in C_v}\mathrm{DP}[u]+1$

これで、最長のパスグラフが $Ans$ に記録される。

Python3

def solve(n, edges):
    links = [[] for _ in range(n)]
    for a, b in edges:
        a -= 1
        b -= 1
        links[a].append(b)
        links[b].append(a)
    degrees = [len(links[i]) for i in range(n)]

    dp = [-1] * n
    q = [0]
    ans = 1
    while q:
        u = q[-1]
        if dp[u] == -1:
            dp[u] = -2
            for v in links[u]:
                if dp[v] == -1:
                    q.append(v)
            continue
        q.pop()

        if degrees[u] < 3:
            dp[u] = 0
            continue
        if degrees[u] == 3:
            dp[u] = 1
            ans = max(ans, 1)
            for v in links[u]:
                if dp[v] > 0:
                    ans = max(ans, dp[v] + 1)
            continue
        mx1 = 0
        mx2 = 0
        dp[u] = 1
        for v in links[u]:
            if dp[v] > 0:
                dp[u] = max(dp[u], dp[v] + 1)
                if mx1 < dp[v]:
                    mx2 = mx1
                    mx1 = dp[v]
                elif mx2 < dp[v]:
                    mx2 = dp[v]
        ans = max(ans, mx1 + mx2 + 1)
    return ans


q = int(input())
for _ in range(q):
    n = int(input())
    edges = [list(map(int, input().split())) for _ in range(n - 1)]
    ans = solve(n, edges)
    print(ans)

G - Div. 1 & Div. 2

• すぬけくんは、主催するプログラミングコンテストに用いる問題の選定をしています。
• $N$ 個の問題案があり、問題案 $i$ の 難易度 は $i$、ジャンル は $K_i$、面白さ は $A_i$ です。
• すぬけくんは以下の制約の上で6問を選定します。
  • 問題案の中から $6$ つの問題案を選ぶ。選ぶ問題案の番号を昇順に $i_1,i_2,\dots,i_6$ とする。
  • 問題案 $i_1,i_2,i_3,i_4$ は相異なるジャンルのものでなければならない。すなわち、$K_{i_1},K_{i_2},K_{i_3},K_{i_4}$ は相異なる必要がある。
  • 問題案 $i_3,i_4,i_5,i_6$ は相異なるジャンルのものでなければならない。すなわち、$K_{i_3},K_{i_4},K_{i_5},K_{i_6}$ は相異なる必要がある。

• 条件を満たすような $6$ 問の選び方が存在するか判定し、存在する場合は選ぶ $6$ 問の面白さの総和の最大値を求めてください。

• $6\leq N \leq 10^5$
• $1\leq K_i \leq N$
• $1\leq A_i \leq 10^9$
• 入力は全て整数

なんとなく、

• $\mathrm{DP}_仮[i,S]:=i$ 番目まで考慮して、ジャンルの集合 $S$ を採用したときのスコア

みたいにしたいが、このままでは問題がある。

• とても全ての $S$ の状態は持てない。
• $S$ は完全な集合ではダメで、採用順序が必要になることがある。

1つめに関しては、割と取り方の自由度は高いので、 途中までのスコアがあまりに低いものが最終的に逆転する、ということも少なそう。 理論的に「上位何個かのみ保持すれば十分」みたいなことが証明できれば嬉しいが、、、

2つめに関して、$5,6$ 番目は、$1,2$ 番目に採用したジャンルでも採用できるが、$3,4$ 番目に採用したジャンルは採用できない。
よって、$1,2$ 番目と $3,4$ 番目の採用ジャンルは区別できる必要があり、更に状態数が増えてしまう。

結局、上位何個かだけ保持するという発想は正しいが、素直なDPでは無理があり、もう少し工夫が必要となる。

• 解説 - AtCoder Beginner Contest 447

まだちゃんと読んで理解できてない。

頭の良い乱択解法。Color Coding が使える。

• 解説 - AtCoder Beginner Contest 447

そもそもこの問題は、$1,2,3,4$ 番目、$3,4,5,6$ 番目で被ってはダメという、4要素にわたる重複禁止制約がきつい。 （4つめを選ぶとき、その前3つで選択したジャンルを覚えておかないといけない）

Color Coding を上手く使うと、これを「$1,2$、$3,4$、$5,6$ のそれぞれで被ってはダメ」という、2つずつの制約に分離できる。

ジャンルを2色 $(0,1)$ に色分けし、 「$1,2,5,6$ は色 $0$ から」「$3,4$ は色 $1$ から」選択する、という制約を課した問題を解くことにする。すると、

• $3,4$ を選択するとき、$1,2$ を覚えておかなくても、自然とジャンルが被ることを阻止できる。
• $5,6$ を選択するとき、$3,4$ を覚えておかなくても、自然とジャンルが被ることを阻止できる。

よって記憶すべき状態が非常に少なくなり、ある色分けに対し $O(N)$ で、その色分けにおける最適解が求められる。

真の最適解において $1,2,3,4,5,6$ 番目で選択する要素のジャンルに、 それぞれ適切に $(0,0,1,1,0,0)$ の色が割り当てられることが、正しく答えが求められる条件である。

色分けにおいて、ランダムに $(0,1)$ を $1/2$ で割り当てると、確率 $1/64$ 以上で正しくなる。
よりよい方法としては、$0$ を $2/3$、$1$ を $1/3$ で割り当てるようにすると、確率 $16/729$ 以上で正しくなる。

$500$ 回ほど繰り返すと、十分な精度（誤答率 $10^{-5}$ 以下）で、 1回は最適解の色が割り当てられることが期待できる。

Python3

import random


def solve(n, problems):
    # Color Coding
    kkk, aaa = zip(*problems)
    NINF = -1 << 60

    # kkk を 0～ジャンルの種類数 にノーマライズ
    kkk_values = sorted(set(kkk))
    mapping = {k: i for i, k in enumerate(kkk_values)}
    kkk = [mapping[k] for k in kkk]
    m = len(kkk_values)

    def update_top2(dp, k, a):
        if dp[0] == k:
            if dp[1] < a:
                dp[1] = a
        elif dp[1] < a:
            dp[2] = dp[1]
            dp[0] = k
            dp[1] = a
        elif dp[2] < a:
            dp[2] = a

    def trial():
        groups = random.choices((0, 0, 1), k=m)
        dp1 = [-1, NINF, NINF]
        dp2 = NINF
        dp3 = [-1, NINF, NINF]
        dp4 = NINF
        dp5 = [-1, NINF, NINF]
        dp6 = NINF
        for i in range(n):
            k = kkk[i]
            a = aaa[i]
            if groups[k] == 0:
                dp2 = max(dp2, (dp1[2] if dp1[0] == k else dp1[1]) + a)
                update_top2(dp1, k, a)
                dp6 = max(dp6, (dp5[2] if dp5[0] == k else dp5[1]) + a)
                update_top2(dp5, k, dp4 + a)
            else:
                dp4 = max(dp4, (dp3[2] if dp3[0] == k else dp3[1]) + a)
                update_top2(dp3, k, dp2 + a)
        return dp6

    TRIAL_COUNT = 500
    ans = max(trial() for _ in range(TRIAL_COUNT))
    if ans < 0:
        return -1
    return ans


n = int(input())
problems = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, problems)
print(ans)