🚶

# ABC188 E - Peddler

2021/01/14に公開

動的計画法

ABC188 E - Peddler

問題へのリンク

問題概要

$N$ 個の街と $M$ 個の一方通行の道がある。街 $X_i$ から $Y_i$ へ道を使って移動できる場合必ず $X_i < Y_i$ である。
各街の金の値段は $A_i$ であり、どこかの街で買って道を使って移動し別の街で売る。利益((金を売った価格) - (金を買った価格))の最大値を求める(マイナスになることもある)。

制約

$2 \leqq N \leqq 2 * 10^5$
$1 \leqq M \leqq 2 * 10^5$
$1 \leqq A_i \leqq 10^9$
$1 \leqq X_i < Y_i \leqq N$

ABC中の解答

残り時間30分ほどしかなかったため途中でタイムアップ。コーディングしていたけどその後すぐ上書きで復習したためコードも残ってない。
辺の情報を片方の街にしか持たせない要因して、各街からの深さ優先探索でまずはやってみようとしていたと思う。

公式解法1

DAG (Directed Acyclic Graph, 閉路を含まない有向グラフ)の場合は以下のようなDPを考えればよいとそうだ。 (DPは苦手なので早く慣れたい)

$dp[i]$ : 街 $i$ に到達できる街 (街 $i$ 自身を含まない) における金の最安値
配るDP : $dp[j] \leftarrow min(dp[j], dp[i], A_i)$

DPの初期値には $1 \leqq A_i \leqq 10^9$ の上限より大きい $10^{10}$ を入れておく。
こうすることで各 $dp[i]$ 計算後に $A_i - dp[i]$ を計算すればその最大値が答えとなる。

他の街から移動してこれない街があるケースもあるが初期値に $10^{10}$ を入れておけば初期値のまま変化しないので $A_i - dp[i]$ が自然と最小値になり候補から外れる。

from collections import defaultdict
import numpy as np

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))

G = defaultdict(list)
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)

# dp[i] : 街iに到達できる街 (街i自身を含まない) における金の最安値
# 配るDP : dp[j] <- min(dp[j], dp[i], Ai)
MAX = 10**10
dp = np.array([MAX] * N)
for at in range(N):
    for to in G[at]:
        dp[to] = min(dp[to], dp[at], A[at])

ans = (A - dp).max()
print(ans)

公式解法2

金の取引価格が一番低い街 $x_1$ から順に以下の行動を行う。

$x_1$ からたどり着ける街 $y$ をすべて列挙し、 $x_1$ で買い $y$ で売った場合の利益を記録する
$y$ を記録しこの後の作業ではたどり着ける街の候補から外す
$x_2, x_3, \dots$ と順番に同様の作業を繰り返す

$y$ を記録しこの後の作業ではたどり着ける街の候補から外す理由は $x_1$ , $x_2$ どちらからも $y$ にたどり着けるなら $x_1$ で買って $y$ で売ったほうが利益が大きいので考慮する必要がないからだ。
作業終了時の一番高い利益が答え。

答えはマイナスになることもあるので初期値に $-10^{10}$ をもたせることができなかった。
苦肉の策としてはじめに見つけた値を入れるようにした。どうすればよりよいかまた調べておきたい。

from collections import defaultdict
import numpy as np

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))

G = defaultdict(list)
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    G[x].append(y)

ranks = np.argsort(A)
seen = np.zeros((N), dtype='bool')

rank = ranks[0]
seen[rank] = True
ans = 0  # -10**10
for key, value in G.items():
    if value:
        ans = A[value[0]] - A[key]
        break
for rank in ranks:
    seen[rank] = True
    q = [rank]
    V = []
    while q:
        at = q.pop()
        for to in G[at]:
            if seen[to]:
                continue
            seen[to] = True
            q.append(to)
            V.append(A[to])
    if V:
        ans = max(ans, max(V) - A[rank])
print(ans)