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

AtCoder Beginner Contest 369

E - Sightseeing Tour

問題文

重み付き連結無向グラフに見立てた $N$ 個の島と $M$ 本の橋があります。
橋 $i$ は島 $U_i$ と島 $V_i$ を相互に結んでおり、どちらの方向に移動するにも $T_i$ だけ時間がかかります。
- 自己辺はありませんが、多重辺はあり得ます。
$Q$ 個の問題が与えられるので、各問題に対する答えを求めてください。$i$ 番目の問題は次のようなものです。
- 相異なる $K_i$ 本の橋、橋 $B_{i,1}$, 橋 $B_{i,2}$, $\ldots$, 橋 $B_{i,K_i}$ が与えられます。
- これらの橋をすべて $1$ 回以上わたり、島 $1$ から島 $N$ まで移動するために必要な時間の最小値を求めてください。
- 与えられた橋はどの順で、またどの向きにわたってもかまいません。

制約

$2\leq N \leq 400$
$N-1\leq M \leq 2\times 10^5$
$1\leq U_i \lt V_i\leq N$
$1\leq T_i\leq 10^9$
$1\leq Q\leq 3000$
$1\leq K_i\leq 5$
$1\leq B_{i,1} \lt B_{i,2} \lt \cdots \lt B_{i,K_i}\leq M$
入力はすべて整数
どの $2$ つの島の間もいくつかの橋をわたって移動することができる。

解法

$N$ がそこそこ小さく、$K_i$ が特に小さい。

Froyd-Warshallで、以下を $O(N^3)$ で事前計算できる。

$\mathrm{Dists}[u][v]=u$ から $v$ への最短距離

各クエリに付き、以下を全探索すればよい。

橋を渡る順番 $K_i!$ 通り
各橋を渡る方向 $2^{K_i}$ 通り

この2つが決まれば、「$1$→1本目に通る橋の始点→終点→2本目に通る橋の始点→終点→…→$N$」の距離を $Dists$ から求められる。その中の最小値がクエリへの答えとなる。

全クエリの計算 $O(Q K! 2^{K} K)$ （※$K$ は $K_i$ の上限）は、制約値の代入でおよそ $5.76 \times 10^7$ となる。
制限時間が長いので、間に合う。

もちろん、bitDPをしてもよい。その方が計算量は少なく済む。

Python3

from itertools import permutations


def floyd_warshall(n, dists):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])
    return dists


n, m = map(int, input().split())
INF = 1 << 60
dists = [[INF] * n for _ in range(n)]
for i in range(n):
    dists[i][i] = 0
edges = []
for _ in range(m):
    u, v, t = map(int, input().split())
    u -= 1
    v -= 1
    dists[u][v] = min(dists[u][v], t)
    dists[v][u] = min(dists[v][u], t)
    edges.append((u, v, t))
floyd_warshall(n, dists)
q = int(input())
buf = []
for _ in range(q):
    k = int(input())
    bbb = list(map(int, input().split()))
    bbb = [b - 1 for b in bbb]
    ans = 1 << 60
    for ppp in permutations(bbb):
        for direction in range(1 << k):
            tmp_v = 0
            tmp_t = 0
            for i, p in enumerate(ppp):
                u, v, t = edges[p]
                if direction & (1 << i) == 0:
                    tmp_t += dists[tmp_v][u] + t
                    tmp_v = v
                else:
                    tmp_t += dists[tmp_v][v] + t
                    tmp_v = u
            tmp_t += dists[tmp_v][n - 1]
            ans = min(ans, tmp_t)
    buf.append(ans)

print('\n'.join(map(str, buf)))

F - Gather Coins

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。
このグリッドの上から $i$ 行目、左から $j$ 列目にあるマスのことを $(i,j)$ と表記します。
このグリッド上には $N$ 枚のコインが落ちており、$i$ 個目のコインはマス $(R_i,C_i)$ を通ることで拾うことができます。
あなたの目標は、マス $(1,1)$ から始めて下か右に $1$ マス移動することを繰り返し、できるだけ多くのコインを拾いながらマス $(H,W)$ まで行くことです。
あなたが拾うことのできるコインの枚数の最大値、およびそれを達成するための移動経路を $1$ つ求めてください。

制約

$2\leq H,W \leq 2\times 10^5$
$1\leq N \leq \min(HW-2, 2\times 10^5)$
$1\leq R_i \leq H$
$1\leq C_i \leq W$
$(R_i,C_i)\neq (1,1)$
$(R_i,C_i)\neq (H,W)$
$(R_i,C_i)$ は互いに相異なる
入力は全て整数

解法

$H \times W$ が小さければ、よくある経路数え上げDPのようにできるが、今回は大きいのでTLEとなる。

$\mathrm{DP_{TLE}}[i][j]:=i$ 行 $j$ 列までに獲得できるコインの最大枚数

ただ、$H \times W$ の配列を一度に持たなくても、1行毎に使い回せば最大枚数だけは求められる。

$\mathrm{DP_{枚数}}[j]:=j$ 列までに獲得できるコインの最大枚数

これは、DP配列をセグメント木で実装して、$(r,c)$ に置いてあるコインを拾う場合は

$\displaystyle \mathrm{DP_{枚数}}[c]=\max_{1 \le i \le c}(\mathrm{DP_{枚数}}[i])+1$ で更新する

とすればよい。$(r,c)$ の小さい順に処理していけばよい。
最終的な $\max(\mathrm{DP_{枚数}})$ が答えとなる。

経路を復元するためには、ここに「コイン $i$ の直前には、どのコインを取ったか」の情報があればよい。

$\mathrm{DP}[j]:=j$ 列までに獲得できるコインの(最大枚数, 最後に取ったコイン番号)
$\mathrm{Predecessor}[i]:=$ 最大値を実現する上でコイン $i$ の直前に取ったコイン番号

これで、最大値を得るために通過したコインをバックトレースできる。

Python3

class SegmentTreeInjectable:
    """
    単位元生成関数 identity_factory と二項演算関数 func を外部注入するセグメント木

    [生成]
    SegmentTreeInjectable(n, identity_factory, func)
    SegmentTreeInjectable.from_array(array, identity_factory, func)  # 既存の配列より作成

    [関数]
    add(i, x)               Aiにxを加算
    update(i, x)            Aiをxに書き換え
    get_range(a, b)         [a, b) の集約値を得る
    get_all()               全ての集約値を得る
    get_point(i)            Aiを得る
    leftmost(a, b, x, ev)   [a, b) の範囲で、ev(x, Ai)=True となる最も左の i を得る（前提条件あり）
    rightmost(a, b, x, ev)  [a, b) の範囲で、ev(x, Ai)=True となる最も右の i を得る（前提条件あり）
    debug_print()           深さ毎に整形して出力する
    """

    def __init__(self, n, identity_factory, func):
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [identity_factory() for _ in range(n2 << 1)]
        self.func = func
        self.idf = identity_factory

    @classmethod
    def from_array(cls, arr, identity_factory, func):
        """ 既存の配列から生成 """
        ins = cls(len(arr), identity_factory, func)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = func(ins.tree[l], ins.tree[r])
        return ins

    def add(self, i, x):
        """
        Aiにxを加算
        :param i: index (0-indexed)
        :param x: add value
        """
        i += self.offset
        self.tree[i] = self.func(self.tree[i], x)
        self.__upstream(i)

    def update(self, i, x):
        """
        Aiの値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        self.__upstream(i)

    def __upstream(self, i):
        tree = self.tree
        func = self.func
        while i > 1:
            i >>= 1
            lch = i << 1
            rch = lch | 1
            tree[i] = func(tree[lch], tree[rch])

    def get_range(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        tree = self.tree
        func = self.func
        result_l = self.idf()
        result_r = self.idf()

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result_r = func(tree[r - 1], result_r)
            if l & 1:
                result_l = func(result_l, tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return func(result_l, result_r)

    def get_all(self):
        return self.tree[1]

    def get_point(self, i):
        return self.tree[i + self.offset]

    def leftmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最初の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        r_found = -1
        while l < r:
            if l & 1:
                if ev(x, tree[l]):
                    return self._leftmost_sub(l, x, ev)
                l += 1
            if r & 1:
                if ev(x, tree[r - 1]):
                    r_found = r - 1
            l >>= 1
            r >>= 1

        if r_found == -1:
            return -1

        return self._leftmost_sub(r_found, x, ev)

    def _leftmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も左のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l]):
                i = l
            else:
                i = l + 1
        return i - self.offset

    def rightmost(self, a, b, x, ev):
        """
        [a, b) の範囲で、ev(x, 値) = True となる最後の index を得る。存在しない場合は-1。

        使用できる条件:
        [l, r) の集約値を y としたとき、ev(x, y)=True となることが、
        l <= i < r 内に ev(x, Ai)=True となる要素があることと等しい。（(func, ev) = (min,ge), (max,le) など）
        """
        tree = self.tree
        l = a + self.offset
        r = b + self.offset
        l_found = -1
        while l < r:
            if r & 1:
                if ev(x, tree[r - 1]):
                    return self._rightmost_sub(r - 1, x, ev)
            if l & 1:
                if ev(x, tree[l]):
                    l_found = l
                l += 1
            l >>= 1
            r >>= 1

        if l_found == -1:
            return -1

        return self._rightmost_sub(l_found, x, ev)

    def _rightmost_sub(self, i, x, ev):
        """
        tree-index i が示す範囲で、ev(x, Aj)=True となる最も右のarray-index j を得る
        （tree[i] が示す範囲には条件を満たすものが必ず存在する前提とする）
        """
        tree = self.tree
        while i < self.offset:
            l = i << 1
            if ev(x, tree[l + 1]):
                i = l + 1
            else:
                i = l
        return i - self.offset

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.tree[i:i * 2])
            i <<= 1


def encode(cnt, idx):
    return cnt << 20 | idx


def decode(key):
    idx = key & 0b11111_11111_11111_11111
    cnt = key >> 20
    return cnt, idx



h, w, n = map(int, input().split())
coins = []
for _ in range(n):
    r, c = map(int, input().split())
    coins.append((r - 1, c - 1))


NINF = -1 << 60
sgt = SegmentTreeInjectable(w, lambda: NINF, max)
sgt.update(0, 0)
predecessor = [-1] * (n + 1)
coins.sort()
for i, (r, c) in enumerate(coins, start=1):
    key = sgt.get_range(0, c + 1)
    cnt, idx = decode(key)
    predecessor[i] = idx
    new_key = encode(cnt + 1, i)
    sgt.update(c, new_key)

best = sgt.get_all()
cnt, idx = decode(best)
i = h - 1
j = w - 1
ans = []
while idx > 0:
    r, c = coins[idx - 1]
    ans.extend(['D'] * (i - r))
    ans.extend(['R'] * (j - c))
    i = r
    j = c
    idx = predecessor[idx]
ans.extend(['D'] * i)
ans.extend(['R'] * j)
ans.reverse()
ans = ''.join(ans)
print(cnt)
print(ans)

G - As far as possible

問題文

$N$ 頂点からなる木が与えられます。
- $i$ 番目（ $1\leq i\leq N-1$ ）の辺は頂点 $U_i$ と頂点 $V_i$ を結んでおり、長さは $L_i$ です。
$K=1,2,\ldots, N$ について次の問題を解いてください。
- 高橋君と青木君がゲームをします。ゲームは次のように行われます。
  - まず、青木君が木上の相異なる $K$ 個の頂点を指定します。
  - 次に、高橋君は始点と終点がともに頂点 $1$ であるような歩道であって、青木君が指定した頂点をすべて通るようなものを構成します。
  - 高橋君が構成した歩道の長さをスコアと定義します。高橋君はスコアをなるべく小さく、青木君はスコアをなるべく大きくしたいです。
  - $2$ 人が最善に行動したときのスコアを求めてください。

制約

$2\leq N\leq 2\times 10^5$
$1\leq U_i \lt V_i\leq N$
$1\leq L_i\leq 10^9$
入力はすべて整数
与えられるグラフは木である。

解法

青木君が $N$ 頂点全てを指定したときは、明らかにオイラーツアーの距離（＝全辺の長さの2倍）である。

ここから、指定頂点を減らしていくことを考える。

頂点 $1$ および $1$ を根とした時に葉となる頂点以外は、指定から除外しても変わらない。（結局、葉まで行かないといけないので）

さて、いよいよ葉のいずれかを指定から除外しなければいけなくなったとする。

    ①
  ／  ＼        ○: 葉以外
 ②     ③      ●: 葉
 /\   ／｜＼
❶④ ⑤ ❹ ⑥
  ｜ ｜    /\
  ❷ ❸   ❺❻

この時、「最後の分岐から葉（自身）までの距離」が短い方から順に除外する、ということを繰り返すとよい。

❶❷にとっては最後の分岐は②、❸❹にとっては③、❺❻にとっては⑥となる。
葉を取り除くと、ゲームのスコアからは「分岐から葉までの距離の往復分」が引かれる。
なるべく青木君は引かれるスコアが小さい方から貪欲に除外していくのが適切である。（本当に？）

ただし、各頂点にとっての “最後の分岐” は変化しうる。
例えば❺を取り除くと、❻は⑥で分岐しなくなり、“最後の分岐” がより根に近い③になる。
分岐する頂点 $v$ の子の中で最も選ばれるのが遅い子（＝最も $v$ までの距離が遠い葉を持つ子）について、このように最後の分岐までがより遠くなり、引かれるスコアが増加する。

以上を踏まえて、以下の木DPをすればよい。

$\mathrm{DP}[v] :=$ 頂点 $v$ の部分木内で最も $v$ から遠い頂点までの距離。
$\mathrm{Drop} :=$ 葉を指定から除外することで引かれるスコア差分の多重集合。最初は空で、木DPの過程で確定したものから追加。

子を複数持つ頂点では、「最も遠い葉を持つ子の値を親に引き継ぎ、残りの子の値は確定するのでDropに追加」という処理をする。

$f(v) := DP[v]+(vとvの親を結ぶ辺の距離)$ とする。

例えば⑥を処理する段階では、

2つの子の $f(❺)$ と $f(❻)$ を比較する。ここで、$f(❻)$ の方が大きかったとする。
$f(❺)$ をDropに登録する。
$DP[⑥]=f(❻)$ とし、$❻$ を除外するコストは確定させず親に引き継ぐ。

のように遷移していく。③でも同様に、

$f(⑤),f(❹),f(⑥)$ を比較する。$f(⑤)$ が最も大きいとする。
$f(❹)$ と $f(⑥)$ をDropに登録する。
$DP[③]=f(⑤)$ とする。

このようにしていくとDropには、いずれかの葉を指定から除外したときに引かれるスコア（の半分）が蓄積される。

ソートして小さい方から除外していくことで、$K$ の大きい方から答えが求められる。

Python3

n = int(input())
links = [set() for _ in range(n)]
all_ans = 0
for _ in range(n - 1):
    u, v, l = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((v, l))
    links[v].add((u, l))
    all_ans += l

remove_q = []
q = [0]
max_depth = [-1] * n
while q:
    u = q[-1]
    if max_depth[u] == -1:
        max_depth[u] = -2
        for v, _ in links[u]:
            if max_depth[v] == -1:
                q.append(v)
    else:
        q.pop()
        tmp_max = 0
        for v, l in links[u]:
            if max_depth[v] < 0:
                continue
            tmp = max_depth[v] + l
            if tmp_max < tmp:
                if tmp_max != -1:
                    remove_q.append(tmp_max)
                tmp_max = tmp
            else:
                remove_q.append(tmp)
        max_depth[u] = tmp_max

remove_q.sort()
ans = [all_ans]
for a in remove_q:
    ans.append(ans[-1] - a)
ans.reverse()
ans.extend([all_ans] * (n - len(ans)))
ans = [a * 2 for a in ans]
print('\n'.join(map(str, ans)))

目次

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

E - Sightseeing Tour

問題文

制約

解法

F - Gather Coins

問題文

制約

解法

G - As far as possible

問題文

制約

解法