AtCoder Beginner Contest 188 E – Peddler をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 188 E – Peddler

一見簡単そうに見えるが、意外ときちんと考えなければならない問題。あらかじめトポロジカルソートされていることに気づけば、それを利用できる。

# AtCoder Beginner Contest 188 E - Peddler
# https://atcoder.jp/contests/abc188/tasks/abc188_e
# tag: グラフ DP 高橋国

# 問題の条件より、町はあらかじめトポロジカルソートされていると
# みなすことが出来る。
# よって、DPの要領で左側から順番に値を決定していけば良さそう。

# 決定していく値は、その町に到着するまでに通った町における、
# 一番安い金の価格とすればいい。

# これにより、それぞれの町において、過去一番安いところで
# 金を買った場合の金額を求められるので、それを元に
# それぞれの町で金を売った場合の利益を計算できる。
# その利益の最大値が答えとなる。

def main():
N, M = map(int, input().split())
prices = list(map(int, input().split()))
path_dat = [list(map(int, input().split())) for _ in range(M)]

paths = [[] for _ in range(N)]
for a, b in path_dat:
paths[a-1].append(b-1)

# それぞれの町より手前の町での一番安い金の価格を
# 配るDPで決定していく。
result = -10**10
min_buy_prices = [10**10] * N
for now in range(N):
# 次の町での金の最小価格は、今の町より前での金の最小価格と、
# 今の町での金の価格のどちらか安い方。
# (を、全ての経路において確認したものになる)
pr = min(min_buy_prices[now], prices[now])
for nxt in paths[now]:
min_buy_prices[nxt] = min(min_buy_prices[nxt], pr)

# 今いる街で金を売った場合の売買の利益を計算する。
profit = prices[now] - min_buy_prices[now]
if result < profit:
result = profit

print(result)

main()

せっかくなので、再帰で逆方向からも解いてみた。

# Xi < Yi の条件により、閉路は存在せず、全ての経路は
# どこかで終端になる。
# そこで、ここではメモ化再帰を用いて解いてみる。
# すなわち、get_max_price(x): x から到達可能な町での、
# 最も高い金の価格を返す。
# 終了条件は、経路の終端。ここでは売れる地点がないので、
# 仮に -inf を返すことにする。

import sys
sys.setrecursionlimit(10**9)
def main():
N, M = map(int, input().split())
prices = list(map(int, input().split()))
path_dat = [list(map(int, input().split())) for _ in range(M)]

paths = [[] for _ in range(N)]
for a, b in path_dat:
paths[a-1].append(b-1)

memo = [None] * N

# 再帰関数による定義。
def get_max_price(x):
if memo[x] != None:
return memo[x]
result = -10**10

for nxt in paths[x]:
result = max(result, prices[nxt], get_max_price(nxt))

memo[x] = result
return result

# 改めて、全地点を調べて最大利益を求める。
result = -10**10
for i in range(N):
buy = prices[i]
sell = get_max_price(i)
if result < sell - buy:
result = sell - buy

print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です