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

AtCoder Beginner Contest 416

E - Development

問題文

AtCoder 国には $1$ から $N$ の番号がついた $N$ 個の街と、$M$ 本の道路、$K$ 個の空港があります。
- $i$ 番目の道路は街 $A_i$ と街 $B_i$ を双方向に結び、移動に $C_i$ 時間かかります。
- 空港は街 $D_1,\ldots,D_K$ にあり、空港がある街同士は $T$ 時間で移動できます。
$Q$ 個のクエリが与えられるので順に処理してください。クエリは次の $3$ 種類のいずれかです。
- '1 x y t': 街 $x$ と街 $y$ を双方向に $t$ 時間で結ぶ道路が作られる。
- '2 x': 街 $x$ に空港が作られる。
- '3': $f(x,y)$ を、街 $x$ から街 $y$ へ道路と空港を使って到達可能なときその最短時間、到達不可能なとき $0$ とする。$\sum_{x=1}^{N}\sum_{y=1}^{N}f(x,y)$ を求める。

制約

$1 \leq N \leq 500$
$0 \leq M \leq 10^5$
$1 \leq A_i \lt B_i \leq N$
$1 \leq C_i \leq 10^9$
$0 \leq K \leq N$
$1 \leq T \leq 10^9$
$1 \leq D_1 \lt \dots \lt D_K \leq N$
$1 \leq Q \leq 1000$
$1$ 種類目のクエリにおいて、$1\leq x \lt y \leq N$, $1 \leq t \leq 10^9$
$2$ 種類目のクエリにおいて、$1 \leq x \leq N$
入力は全て整数

解法

グラフ探索におけるちょっとした応用の組合せ。

Froyd-Warshall で求めた全点間距離は、辺を1本追加した場合の更新を $O(N^2)$ でおこなえる
$k$ 個の頂点が互いに同コストで行き来できる場合、直接辺を張ると $O(k^2)$ 本の辺が必要になってしまうが、ハブ的な頂点を作って仲介すると $O(k)$ 本の辺で済む

最初に Froyd-Warshall で $O(N^3)$ かけて全点間距離の総和を求め、クエリ1,2がきたら $O(N^2)$ かけて総和を差分更新していけば、全体 $O(N^3+N^2Q)$ で求められそう。制約を代入すると $3.75 \times 10^8$ で若干心配だが、実行制限時間が3.5秒で、また処理が非常にシンプルで定数倍が軽いので、まぁ大丈夫だろう。

クエリ1で頂点 $x,y$ を結ぶコスト $t$ の無向辺を追加した場合、 2頂点 $(i,j)$ 間の距離は以下になり、各組につき $O(1)$、全体 $O(N^2)$ で更新できる。

$d(i,j)←\min(d(i,j),d(i,x)+c+d(y,j),d(i,y)+c+d(x,j))$

空路の移動は、「空路」を表す頂点 $p$ を1つ追加し、空港のある頂点と $p$ をコスト $\frac{T}{2}$ の無向辺で接続しておくと正しく表現できる。
クエリ2で $x$ に空港が新設されるのは、クエリ1で $(x,p)$ 間にコスト $\frac{T}{2}$ の辺が追加されたと読み替えられる。

実装上は、全てのコストを2倍しておくとやりやすい。

注意点として、「地上頂点から空路頂点 $p$ への距離」は、最初の総和を求める時や、差分更新の時に含めてはいけない。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n, m = inp[:2]
    aaa = inp[2:2 + 3 * m:3] - 1
    bbb = inp[3:2 + 3 * m:3] - 1
    ccc = inp[4:2 + 3 * m:3] * 2
    k = inp[2 + 3 * m]
    t = inp[3 + 3 * m]
    ddd = inp[4 + 3 * m:4 + 3 * m + k] - 1
    q = inp[4 + 3 * m + k]
    queries = inp[5 + 3 * m + k:]

    INF = 1 << 60
    dp = np.full((n + 1, n + 1), INF, np.int64)
    for i in range(n + 1):
        dp[i, i] = 0
    for i in range(m):
        dp[aaa[i], bbb[i]] = dp[bbb[i], aaa[i]] = min(dp[aaa[i], bbb[i]], ccc[i])
    for i in range(k):
        dp[ddd[i], n] = t
        dp[n, ddd[i]] = t

    for k in range(n + 1):
        for i in range(n + 1):
            for j in range(n + 1):
                dp[i, j] = min(dp[i, j], dp[i, k] + dp[k, j])

    ans = []
    tmp = 0
    for i in range(n):
        for j in range(n):
            if dp[i, j] < INF:
                tmp += dp[i, j]

    qi = 0
    for _ in range(q):
        op = queries[qi]
        if op == 1:
            x = queries[qi + 1] - 1
            y = queries[qi + 2] - 1
            c = queries[qi + 3] * 2
            qi += 4
            for i in range(n + 1):
                for j in range(n + 1):
                    old = dp[i, j]
                    new = min(dp[i, x] + c + dp[y, j], dp[i, y] + c + dp[x, j])
                    if old > new:
                        if i < n and j < n:
                            if old == INF:
                                tmp += new
                            else:
                                tmp -= old - new
                        dp[i, j] = new
        elif op == 2:
            x = queries[qi + 1] - 1
            qi += 2
            for i in range(n + 1):
                for j in range(n + 1):
                    old = dp[i, j]
                    new = min(dp[i, x] + t + dp[n, j], dp[i, n] + t + dp[x, j])
                    if old > new:
                        if i < n and j < n:
                            if old == INF:
                                tmp += new
                            else:
                                tmp -= old - new
                        dp[i, j] = new
        else:
            qi += 1
            ans.append(tmp // 2)

    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)))

F - Paint Tree 2

問題文

$1$ から $N$ までの番号がついた $N$ 頂点からなる木 $T$ と整数 $K$ が与えられます。
- $i$ 番目 $(1\le i\le N - 1)$ の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。
- また、頂点 $i$ $(1\le i\le N)$ には整数 $A_i$ が書かれています。
はじめ、全ての頂点は白色で塗られています。
あなたは以下の行動を $0$ 回以上 $K$ 回以下行います：
- 木 $T$ のパスであってそのパスに含まれるどの頂点も白色で塗られているようなパスを選ぶ。
- その後、選んだパスに含まれる頂点を全て黒色で塗る。

行動を終えた後に黒色で塗られた頂点に書かれた整数の総和としてあり得る最大値を求めてください。

制約

$2\le N\le 2\times 10^5$
$1\le K\le 5$
$1\le A_i\le 10^9$
$1\le U_i \lt V_i \le N$
与えられるグラフは木
入力される値は全て整数

解法

$K$ が小さい。適当な頂点を根とした木DPで、「何個のパスを確定させたか」ごとに、スコアの最大値を記録していく方法が採れそう。

$\mathrm{DP}[i,j,k]:=$ 頂点 $i$ を根とした部分木で、$j$ が以下の条件で、$k$ 個のパスを使っている場合のスコア最大値
- $1$: 頂点 $i$ を使っていない
- $2$: 頂点 $i$ を使っているが、親には伸ばせない（正確には、伸ばせるとは限らない）
- $3$: 頂点 $i$ を使い、親にも伸ばせる

j=1 (例はk=2)  j=2 (例はk=1)  j=3 (例はk=1)
    i○            i●            i●
    /  \           /  \           /  \
   ●  ●         ●  ●         ●  ○
   /\  ｜         /\  ｜         /\  ｜
  ●● ●        ●○ ●        ●○ ○

$j=1$ と $2$ は統合可能といえば可能なのだが、頂点 $i$ が複数の子を持つとき、それを1つずつ統合していく過程では分けた方がいいため、 DPへも分けたまま記録することにする。

更新が難しい。丁寧に考えていく。

$i$ について、いくつかの子を統合済みの暫定DPを $dp[j,k]$ とする。ここに子 $c$ を追加した場合を考える。

   i○
  ／｜ + ＼
 ○ ○    ○c
 /\ ｜    ：
○○○

$i$ 側で使っているパスの個数を $p$、$c$ 側で使っているパスの個数を $q$ とする。

$dp[1]$ は、$i$ に $c$ 側をそのまま（パスを統合したりはせず）くっつけるように統合できる。

$dp[1,p+q] \xleftarrow{\max} dp[1,p] + \mathrm{DP}[c,*,q]$
- ※$\mathrm{DP}[c,*,q]$ は、$\max_{j=1,2,3}(\mathrm{DP}[c,j,q])$ とする

$dp[2]$ は、1と同様「$i$ に $c$ 側をそのままくっつける」ほか、「$i$ 側と $c$ 側から伸びるパスをくっつけて1本のパスにする」ことができる。

$dp[2,p+q] \xleftarrow{\max} dp[2,p] + \mathrm{DP}[c,*,q]$
$dp[2,p+q-1] \xleftarrow{\max} dp[3,p] + \mathrm{DP}[c,3,q]$

$dp[3]$ は、「$i$ に $c$ 側をそのままくっつける」「$i$ 側の $dp[1]$ に対して $c$ の $j=3$ からパスを伸ばす」「どちらからもパスを繋げず、$i$ から新しいパスを開始する」ことができる。

$dp[3,p+q] \xleftarrow{\max} dp[3,p] + \mathrm{DP}[c,*,q]$
$dp[3,p+q] \xleftarrow{\max} dp[1,p] + \mathrm{DP}[c,3,q] + A_i$
$dp[3,p+q+1] \xleftarrow{\max} dp[1,p] + \mathrm{DP}[c,*,q] + A_i$

※最後のは、「全ての子について統合し終えた後、$dp[1]$ に対して新しいパスを開始する」ことでもできる。

1頂点につき $O(K^2)$、全体 $O(NK^2)$ で求められる。

Python3

def solve(n, k, aaa, edges):
    links = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        links[u].add(v)
        links[v].add(u)
    q = [0]
    status = [0] * n
    dp = [None] * n
    while q:
        u = q[-1]
        if status[u] == 0:
            status[u] = 1
            for v in links[u]:
                links[v].discard(u)
                q.append(v)
            continue
        q.pop()
        a = aaa[u]

        excluded = [0] * (k + 1)  # excluded[k]: u をパスに含まない中で、パス k 本からなる場合の最大スコア
        closed = [a] * (k + 1)  # closed[k]: u をパスに含むが、親に伸ばせるとは限らない状態での、パス k 本からなる場合の最大スコア
        opened = [a] * (k + 1)  # opened[k]: u をパスに含み、親に伸ばせる状態での、パス k 本からなる場合の最大スコア
        closed[0] = opened[0] = 0
        for v in links[u]:
            exv, clv, opv = dp[v]
            for i in range(k, 0, -1):
                for j in range(1, i + 1):
                    best_j = max(exv[j], clv[j], opv[j])
                    excluded[i] = max(excluded[i], excluded[i - j] + best_j)
                    closed[i] = max(closed[i],
                                    closed[i - j] + best_j,
                                    opened[i - j + 1] + opv[j])
                    opened[i] = max(opened[i],
                                    excluded[i - j] + opv[j] + a,
                                    0 if i == j else opened[i - j] + best_j,
                                    0 if i == j else excluded[i - j - 1] + max(exv[j], clv[j]) + a)

        dp[u] = (excluded, closed, opened)

    ans = max(dp[0][i][k] for i in range(3))
    return ans


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

G - Concat (1st)

問題文

$N$ 個の文字列 $S_1,\ldots,S_N$ が与えられます。
全ての要素が $1$ 以上 $N$ 以下であるような長さ $K$ の数列 $(A_1,\ldots,A_K)$ に対し、文字列 $f(A_1,\ldots,A_K)$ を $S_{A_1}+S_{A_2}+\dots+S_{A_K}$ と定めます。ここで '+' は文字列の連結を表します。
$N^K$ 個の数列全てについての $f(A_1,\dots,A_K)$ のうち辞書順最小の文字列を求めてください。

制約

$1\leq N \leq 10^5$
$1\leq K \leq 10^5$
$S_i$ は英小文字からなる長さ $10$ 以下の文字列
$N,K$ は整数

解法

メインで使う文字列

メインで使う文字列は唯一に決まる。

たとえば S=(at, co, der) の時、at を $K$ 回繰り返したものが答えとなり、他の文字列は使う必要が無い。

S=(c, cb, cba, cbacba) の時は、「cba を $K-1$ 回繰り返し、最後に c を使う」ものが答えとなる。

メインで使う文字列は「無限に繰り返した文字列の辞書順が $S$ の中で最小のもの。同じ中では長さが一番短いもの」となる。
これを（一般的な名称は知らないが）「連結順最小」と呼ぶことにする。
単純に $S$ の中での辞書順最小とは異なる。

連結順最小は、以下のような2項間比較をすることによって求められる。
この比較は全順序を満たすので、（同じ文字列を除けば）連結順最小は唯一に決まる。

2つの文字列 $S,T$ について、$S+T$ が $T+S$ より辞書順で小さいなら、$S \lt T$
$S+T=T+S$ なら、$|S| \lt |T|$ なら $S \lt T$

基本的には連結順最小文字列を $K$ 回繰り返したものが最適となる。
ただし、冒頭の例のように「連結順最小文字列のprefix」となっているような文字列が $S$ にある場合、末尾付近ではそれを使った方が文字列が短くなり、より辞書順が小さくなる可能性がある。

答えの求め方

最後の1回だけを変えればいいとは限らない。
S=(c,cba,cbacbacbaa) の時、連結順最小の cbacbacbaa を $K-3$ 回繰り返した後、末尾を cba cba c とするのが最適となる。

とはいえ、$S_i$ は短く10文字以下なので、連結順最小文字列の prefix となりうる文字列は最大10種類、置き換えが発生しうるのも最大で末尾の10回となる。

「連結順最小文字列 $T$ のprefix」である2つの文字列 $R,S$ について、長さの比較で $|R| \lt |S|$ ならば、連結順は $R \gt S$ となる。
もしそうでない場合、$T$ が連結順最小であることに矛盾する。

よって、末尾を置き換える際も、（使われるとしたら）長さが長い方が先に使われる。
置き換え方のパターン数は高々 ${}_{10}H_{10}=92378$ となり、全探索できる。

$|S_i|$ がそこそこ大きい場合

制約が異なって、$K=100, |S_i|=100$ などの場合、上記の解法は取れない。

この場合、公式Editorial のようにすると間に合う。

$\mathrm{DP}[i,j]:=i$ 個の文字列を使って作れる $T_{\infty}[j:]$ のprefixで、最も短いものの長さ

または、上記の解法をもう少し丁寧に場合分けすれば、探索範囲はもっと小さくできそうなんだけど。。。

Python3

from functools import cmp_to_key
from itertools import combinations_with_replacement


def solve(n, k, sss):
    def cmp(a, b):
        ab = a + b
        ba = b + a
        if ab < ba:
            return -1
        if ab > ba:
            return 1
        return len(a) - len(b)

    sss = set(sss)
    best = min(sss, key=cmp_to_key(cmp))
    candidates = [best]
    for s in sss:
        if len(s) < len(best) and s == best[:len(s)]:
            candidates.append(s)
    candidates.sort(key=len, reverse=True)
    m = len(candidates)

    last_num = min(10, k)
    best_last = best * last_num
    for ppp in combinations_with_replacement(range(m), last_num):
        best_last = min(best_last, ''.join(candidates[p] for p in ppp))
    ans = best * (k - last_num) + best_last

    return ans


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

目次

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

E - Development

問題文

制約

解法

F - Paint Tree 2

問題文

制約

解法

G - Concat (1st)

問題文

制約

解法

メインで使う文字列

答えの求め方

$|S_i|$ がそこそこ大きい場合