# ABC188 E - Peddler

3 min read読了の目安(約2700字

ABC188 E - Peddler

問題へのリンク

https://atcoder.jp/contests/abc188/tasks/abc188_e

問題概要

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)

https://atcoder.jp/contests/abc188/submissions/19431144

公式解法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)

https://atcoder.jp/contests/abc188/submissions/19432643