日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）F,G問題メモ

日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

F - Range Connect MST

• $N + Q$ 頂点のグラフがあり、頂点には $1, 2, \ldots, N + Q$ の番号がついています。グラフにははじめ辺がありません。
• このグラフに対して $i = 1, 2, \ldots, Q$ の順に以下の操作を行います。
  • $L_i \leq j \leq R_i$ を満たす各整数 $j$ について頂点 $N + i$ と頂点 $j$ の間にコスト $C_i$ の無向辺を追加する
• すべての操作を終えた後グラフは連結であるか判定し、連結である場合はこのグラフの最小全域木のコストを求めてください。

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq C_i \leq 10^9$

辺が多すぎるのでTLEになるが、まずはクラスカル法でやるとどういう流れになるか把握する。

$C_i$ が小さい順に辺を取り出し、両端が連結じゃなければその辺を採用する。
同じ $i$ から出る辺は同コストなのでまとめて考えるとして、 はじめのうちは、$L_i～R_i$ の全てに $i$ からの辺が張られていく。

 i      0     1     2     3     4
Ci      9     6     1     4     2
Q側    ○    ○    ○    ○    ○    5本の辺が採用され、
                ／/｜\＼             5 x 1 がコストに計上される
N側    ○○○○○○○○○○○○○
               L2------R2

 i      0     1     2     3     4
Ci      9     6     1     4     2
Q側    ○    ○    ○    ○    ○    3本の辺が採用され、
                ／/｜\＼    ／/｜    3 x 2 がコストに計上される
N側    ○○○○○○○○○○○○○
                           L4--R4

$i=3$ を処理する時、一部は既に他の $i$ により連結になっている。$i=3$ からは連結なうちの1つに対してのみ結びにいけばよい。

 i      0     1     2     3     4
Ci      9     6     1     4     2
Q側    ○    ○    ○    ○    ○
                ／/｜\＼    ／/｜
N側    ○○○○○○○○○○○○○
                 L3----------R3
                 |------|          ←i=3からは、この4つにはどれか1つにのみ結びにいけば十分
                           |--|    ←この2つにも同様、どれか1つにのみ結びにいけば十分

性質上、$N$ 側頂点の連結は「$j=3～11$ の範囲が連結」みたいに連続した範囲となり、 「$j=3,4,8,11$ が連結」のように飛び飛びになることはない。
この「どこからどこまでが結ばれているか」の情報を上手く管理したい。

$N$ 側頂点に対し「自分以降で、少なくともここまでは同一連結成分」という情報を持つ配列 jump を定義する。

初期状態は $jump = [0,1,2,...,N-1]$ である。

$Q$ 側頂点 $i$ を処理する際、$N$ 側頂点を $j=L_i$ から順に見ていく。
$jump[j]=j$ ならそこで連結が途切れているので、そこまでの連結成分と $i$ を結ぶため $C_i$ をコストに加算し、$j+=1$ する。
それ以外の場合、$j←jump[j]$ とする。
$j \ge R_i$ になるまで辿ったら、最後の連結成分と結ぶため、$C_i$ を追加でコストに加算すればOK。

上記の過程で経由した $j$ は、全て $jump[j]←\max(jump[j],jump[Ri])$ に更新していく。

 i      0     1     2     3     4
Ci      9     6     1     4     2
Q側    ○    ○    ○    ○    ○
                ／/｜\＼    ／/｜
N側    ○○○○○○○○○○○○○
jump    0 1 2 3 4 5 6 7 8 9101112
                v v v v     v v
jump    0 1 2 3 8 8 8 8 8 9121212

こうすると、$i=3$ を処理する時、$L_i～R_i$ を全てチェックしなくてもよくなる。

 i      0     1     2     3     4
Ci      9     6     1     4     2
Q側    ○    ○    ○    ○    ○
                ／/｜\＼    ／/｜
N側    ○○○○○○○○○○○○○
jump    0 1 2 3 8 8 8 8 8 9121212
                 L3          R3
                  .     * * .      チェックされる頂点(*はコスト加算される箇所)

あるクエリで $k$ 個の頂点をチェックしたら、次以降、$k$ 個の中で1クエリ中に再度チェックされる頂点は高々2個までになる。
全体で、$O(N+Q)$ で求められる。

最後に、$j=0$ からjumpを辿って $N-1$ に辿り着けるか判定する。（辿り着けなければ連結にできない）

Python3

from operator import itemgetter

n, q = map(int, input().split())
lrc = [tuple(map(int, input().split())) for _ in range(q)]
lrc.sort(key=itemgetter(2))
jump = list(range(n))
ans = 0
for l, r, c in lrc:
    l -= 1
    r -= 1

    t = jump[r]
    i = l
    while i < r:
        if jump[i] == i:
            ans += c
            jump[i] = t
            i += 1
        else:
            t = max(t, jump[i])
            ni = jump[i]
            jump[i] = t
            i = ni
    ans += c

if any(jump[i] == i for i in range(n - 1)):
    print(-1)
else:
    print(ans)

• 解説 - 日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

連結性を考えたとき、辺が下記のように張られるものと捉えなおしても問題ない。

• $Q$ 側の $i$ と $L_i$ を結ぶ辺
• $L_i～R_i$ を横に結ぶ辺

Q側    ○       ○     _ ○ _     ○     _ ○
                     ／ /｜\ ＼        ／ /｜    元の問題の辺の張り方
N側    ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

                         ↓

Q側    ○       ○     _ ○       ○     _ ○
                     ／                ／        捉えなおした辺の張り方
N側    ○ ○ ○ ○ ○-○-○-○-○ ○ ○-○-○

すると、$i→L_i$ の辺は必ず必要なので $\sum_i{C_i}$ は別計上するとして、 $N$ 側を横に結ぶ辺は、その中で最小コストの辺を使えば良いことになる。

遅延評価セグメント木を使うこともできるが、イベントソートでも解ける。

イベントソートすることで、「隣接2頂点間に張られている辺コスト $C_i$ の集合が同じである区間」をまとめて処理できる。
要素削除可能なヒープキューで $C_i$ の集合を管理することで、各区間の最小 $C_i$ を取得できる。

途中でヒープキューが空になったらアウト。

計算量は $O(Q\log{Q})$ となり、大きい $N$ にも耐えられる。

G - Last Major City

• 都市と道路に見立てた、$N$ 頂点 $M$ 辺の無向連結グラフが与えられます。
• いくつかの道路に拡張工事を行います。道路 $i$ の拡張にかかるコストは $C_i$ です。
• $i=K,K+1,\dots,N$ について、以下の問いに答えてください。
  • 主要都市として都市 $1,2,...,K-1$ および $i$ の $K$ 個を指定する。
  • どの主要都市間も、拡張された道路のみを辿って行き来可能としたい。
  • 必要な拡張工事のコストの総和の最小値はいくつか。

• $2\leq N \leq 4000$
• $N-1\leq M \leq 8000$
• $2\leq K \leq \min(N,10)$
• $1\leq A_i \lt B_i \leq N$
• $1\leq C_i \leq 10^9$

最小シュタイナー木。
わりと知識問題であり、アルゴリズムを知っていたらその過程で得られる情報がそのまま答えとなるのに気付くのは容易い。

• シュタイナー木
• My Algorithm : kopricky アルゴリズムライブラリ

最小シュタイナー木問題は、ぱっと見、それっぽい近似値は出せそうではあるが、厳密解はNP困難である。
厳密解を求める方法として Dreyfus–Wagner法が知られる。

連結にしたい頂点（問題中の“主要都市”）を「ターミナル」と呼ぶ。

• $DP[S][v]=$ ターミナルの部分集合 $S$ およびターミナルとは限らない頂点 $v$ を連結にするのに必要な最小コスト

• 初期状態
  • 各ターミナル $t$ につき $DP[\{t\}][t]=0$、他はINF

$S$ が小さい方から求めていけば、最終的な結果から各 $v=K,K+1,...,N$ に対し $DP[\{1,2,...,K-1\}][v]$ が答えとなる。

遷移について、$DP[S][v]$ は以下の最小値となる。

• ① $S$ を $T$ と $U$ の2つに分けた時、$DP[T][v]+DP[U][v]$
• ② 辺 $(w,v)$（コスト $c$）を介して、$DP[S][w]+c$

①は、部分集合を全探索するbitDPによくあるやつで、 全体を通して $3^K$ かかり、それが各 $v$ に対し発生するので $O(N 3^K)$

②は、①で更新した後、全頂点を始点としたDijkstraでコストが小さい方から更新していく。
計算量は$O(2^K (N+M)\log{N})$ となる。

Python3

from heapq import heapify, heappop, heappush
from typing import Tuple, List


def minimum_steiner_tree(links: List[List[Tuple[int, int]]], terminals: List[int]):
    n = len(links)
    p = len(terminals)

    INF = 1 << 60
    init = [INF] * (1 << p)
    init[0] = 0
    dp = [init.copy() for _ in range(n)]
    for i, t in enumerate(terminals):
        dp[t][1 << i] = 0
    for bitset in range(1, 1 << p):
        # vを介して結合できるグループ
        for v in range(n):
            sub_bitset = bitset
            while sub_bitset > 0:
                dp[v][bitset] = min(dp[v][bitset], dp[v][sub_bitset] + dp[v][bitset ^ sub_bitset])
                sub_bitset = (sub_bitset - 1) & bitset
        # Dijkstraで更新
        q = [(dp[v][bitset], v) for v in range(n)]
        heapify(q)
        while q:
            cost, u = heappop(q)
            if dp[u][bitset] < cost:
                continue
            for v, c in links[u]:
                nc = cost + c
                if dp[v][bitset] <= nc:
                    continue
                dp[v][bitset] = nc
                heappush(q, (nc, v))

    return dp


n, m, k = map(int, input().split())
links = [[] for _ in range(n)]
for _ in range(m):
    u, v, c = map(int, input().split())
    u -= 1
    v -= 1
    links[u].append((v, c))
    links[v].append((u, c))

result = minimum_steiner_tree(links, list(range(k - 1)))
ans = [res[-1] for res in result[k - 1:]]
print('\n'.join(map(str, ans)))