AtCoder Beginner Contest 395 F,G問題メモ

AtCoder Beginner Contest 395

F - Smooth Occlusion

問題文

高橋くんには歯が $2N$ 本あり、$N$ 本は上の歯、残りの $N$ 本は下の歯です。
左から $i$ 本目 $(1\leq i\leq N)$ の上の歯の長さは $U_i$ で、左から $i$ 本目 $(1\leq i\leq N)$ の下の歯の長さは $D_i$ です。
高橋くんの歯が次の $2$ つの条件をどちらも満たしているとき、歯が「うまく噛み合っている」ということにします。
- ある整数 $H$ が存在し、$1\leq i\leq N$ を満たすすべての整数 $i$ について、$U_i+D_i=H$ が成り立つ。
- $1\leq i\lt N$ を満たすすべての整数 $i$ について、$\vert U_i-U_{i+1}\vert\leq X$ が成り立つ。

高橋くんは次の操作を好きなだけ繰り返すことができます。
- $1$ 円を支払って歯削り機を使い、長さが正であるような歯を $1$ つ選んでその歯の長さを $1$ 減らす。
この操作以外の方法で歯の長さを変えることはできません。

高橋くんが歯をうまく噛み合わせるために支払うことになる最小の金額を求めてください。

制約

$2\leq N\leq2\times10 ^ 5$
$1\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)$
$1\leq D _ i\leq10 ^ 9\ (1\leq i\leq N)$
$1\leq X\leq10 ^ 9$
入力はすべて整数

解法

とりあえず2番目の条件だけ考えて、「歯を削る操作だけで、隣り合う上の歯の高さの差を全て $X$ 以下にする」ことを考える。

これは、以下の操作を順におこなえば達成できる。

先頭から $U_{i+1}=\min(U_{i+1},U_i+X)$ とする
末尾から $U_{i-1}=\min(U_{i-1},U_i+X)$ とする

かつ、これが最も削る長さが最小となる。
言い換えれば、「どの削った歯も、あと1単位でも削るのが短ければ、2番目の条件を満たせない」状態となる。

操作後の上の歯の長さ配列を、元の $U$ と区別して $U'$ とおく。

上の歯を削った後、1番目の条件について達成できる $H$ の上限は $h=\min_{1 \le i \le N}{U'_i+D_i}$ となる。
そして $h$ で揃えるのは必ず達成できる（※）ので、$\displaystyle \sum{U}+\sum{D}-HN$ が答えとなる。

（※）上の歯で $U'_i \gt h$ なものは $h$ まで削っても2番目の条件が満たされた状態は保たれる。その他は $D$ 側を削って調整すればよい。

計算量は $O(N)$

Python3

def solve(n, x, teeth):
    uuu, ddd = map(list, zip(*teeth))
    orig = uuu.copy()
    for i in range(1, n):
        uuu[i] = min(uuu[i], uuu[i - 1] + x)
    for i in range(n - 1, 0, -1):
        uuu[i - 1] = min(uuu[i - 1], uuu[i] + x)
    ans = sum(u0 - u1 for u0, u1 in zip(orig, uuu))

    h = min(map(sum, zip(uuu, ddd)))
    ans += sum(uuu) + sum(ddd) - h * n
    return ans


n, x = map(int, input().split())
teeth = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, x, teeth)
print(ans)

G - Minimum Steiner Tree 2

問題文

正整数 $N,K$ が与えられます。また、$N\times N$ 行列 $C=(C_{i,j})$ $(1\leq i,j\leq N)$ が与えられます。ここで、$C_{i,i}=0,C_{i,j}=C_{j,i}$ が保証されます。
頂点に $1,2,\dots,N$ と番号がつけられた $N$ 頂点の重み付き完全グラフがあります。$i\lt j$ なる頂点の組 $i,j$ について、頂点 $i$ と頂点 $j$ を結ぶ辺の重みは $C_{i,j}$ です。
$Q$ 個のクエリが与えられます。$i$ 番目のクエリでは $K+1$ 以上 $N$ 以下の相異なる整数の組 $s_i,t_i$ が与えられるので、以下の問題を解いてください。
- このグラフから $0$ 個以上好きな個数辺と頂点を取り除いてできる連結なグラフのうち、頂点 $1,2,\dots,K,s_i,t_i$ をすべて含むようなものを良いグラフとよびます。
- 良いグラフのコストを、グラフに含まれる辺の重みの総和とします。
- 良いグラフのコストの最小値を求めてください。

制約

$3\leq N\leq 80$
$1\leq K\leq \min(N-2,8)$
$0\leq C_{i,j}\leq 10^9$ $(1\leq i,j\leq N,i\ne j)$
$C_{i,j}=C_{j,i}$ $(1\leq i,j\leq N,i\ne j)$
$C_{i,i}=0$ $(1\leq i\leq N)$
$1\leq Q\leq 5000$
$K+1\leq s_i,t_i\leq N$ $(1\leq i\leq Q)$
$s_i\ne t_i$ $(1\leq i\leq Q)$
入力はすべて整数

解法

最小シュタイナー木問題のアレンジ。
計算量見積もりが難しい。

最小シュタイナー木は、約半年前、ABC-G で出題された。
過去問では、クエリが $(s_i,t_i)$ の2つではなく、1つのみの場合が求められればよかった。

シュタイナー木で必ず含めなければならない頂点を「ターミナル」と呼ぶ。
最小シュタイナー木の重みは、以下のDPで求められる。

$\mathrm{DP}[S,v]:=$ ターミナルの部分集合 $S$ と、ターミナルとは限らない頂点 $v$ を全て含めた部分木の最小コスト

ターミナルの個数を $k$ とすると、完全グラフなので計算量は $O(3^kN + 2^kN^2\log{N})$ がかかる。

クエリが1頂点のみなら、このDPの過程で自然と「全てのターミナルと、他のもう1頂点 $v$ を含めた部分木の最小コスト」が求まっているので、最終的なDP配列を参照すれば求められる。

今回は2頂点だが、制約が小さいので以下で解ける。

各頂点 $v=K+1,...,N$ につき、ターミナルを $\{1,2,...,K,v\}$ とした場合の最小シュタイナー木DPを前計算する。
- $v$ に対するDP結果を $\mathrm{DP}_v$ とする。
クエリ $(s,t)$ に対する答えは、$\mathrm{DP}_s[\{1,2,...,K,s\},t]$ となる。

計算量は $O(3^KN^2 + 2^KN^3\log{N})$ で、制約上限の単純な代入では約 $1.7 \times 10^9$ となり、通るのか？と不安に思うが、計算量の後ろの項（Dijkstra部分）は毎回毎回フルで回されることはなく、すぐ終わることも多いので、意外と間に合う。

また、今回はグラフが密なので、Dijkstraの実装方法も毎回配列から暫定最小値を探すようにすると $O(3^KN^2 + 2^KN^3)$ となり、二分ヒープを使うより高速となる。

$N$ 回DPを回す上記の解法は本番でも検討したが、計算量が無理だと思って他の方法を考えてしまった。間に合うもんだね。

Python3

from heapq import heapify, heappop, heappush

import os
import sys

import numpy as np


def solve(inp):
    n, p = inp[:2]
    ccc = np.ascontiguousarray(inp[2:2 + n * n]).reshape(n, n)
    q = inp[2 + n * n]
    sss = inp[3 + n * n::2] - 1
    ttt = inp[4 + n * n::2] - 1

    INF = 1 << 60
    ddd = np.full((n, n), INF, np.int64)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i != j and j != k and i != k:
                    ddd[i, j] = min(ddd[i, j], ccc[i, k] + ccc[k, j])

    tuple_array = [(n, n)]
    tuple_array.clear()
    links = [tuple_array.copy() for _ in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if ccc[i, j] >= ddd[i, j]:
                continue
            links[i].append((j, ccc[i, j]))
            links[j].append((i, ccc[i, j]))

    def minimum_steiner_tree(links, terminals):
        p = len(terminals)

        INF = 1 << 60
        dp = np.full((n, 1 << p), INF, np.int64)
        dp[:, 0] = 0
        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))

        result = dp[:, -1]
        return result

    steiner = []
    for x in range(p, n - 1):
        terminals = list(range(p)) + [x]
        steiner.append(minimum_steiner_tree(links, terminals))

    ans = []
    for qi in range(q):
        s = sss[qi]
        t = ttt[qi]
        if s < t:
            ans.append(steiner[s - p][t])
        else:
            ans.append(steiner[t - p][s])
    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 395 F,G問題メモ

F - Smooth Occlusion

問題文

制約

解法

G - Minimum Steiner Tree 2

問題文

制約

解法