振り返りです。
AtCoder Beginner Contest 297 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys
from io import StringIO
input = lambda: sys.stdin.readline()[:-1]
def test(f, data):
stdin = sys.stdin
stdout = sys.stdout
sys.stdin = StringIO(data["in"])
out = StringIO()
sys.stdout = out
err = None
try:
f()
except BaseException as e:
err = e
else:
ans = out.getvalue()
exp = data["out"]
sys.stdin = stdin
sys.stdout = stdout
if err: raise err
result = "AC" if exp == ans else "WA"
print(f"{result}: expected: {exp}, output: {ans}")
def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}'), 1):
print(f"case {i}")
test(f, data)
やってみよう！
E関数を完成させて「Run」ボタンをクリックしよう！
test_dataE = [
{
"in":"""4 6
20 25 30 100
""",
"out": """50
"""
},{
"in":"""2 10
2 1
""",
"out": """10
"""
},{
"in":"""10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
""",
"out": """5705443819
"""
},
]
def E():
pass
test_all(E)
自由欄
振り返り
コンテスト中はDPかなぁ～と考えたりしたのですが、うまいこと解法が思いつかず試合終了。
という訳で解説 を見ますが、「探索方法」を一読してもよく理解できません😇
heapqモジュールでたこ焼きの組み合わせによる支払い金額を昇順に探索しています。
def E():
import heapq as hq
N, K = map(int, input().split())
*A, = map(int, input().split())
price = 0
q = A.copy(); hq.heapify(q)
while K:
now = hq.heappop(q)
if not now > price: continue
price = now
for a in A:
hq.heappush(q, now + a)
K -= 1
print(price)
test_all(E)
結果：#40630180
ACしてしまった…
自由欄
ダイクストラ法
これまで名前は見てきたものの、ずっと後回しにしていたダイクストラ法をしっかり理解してみます。ABC257の振り返り でした。大分寝かせてたな…)
AtCoderではABC035 のD - トレジャーハント が有名なようです。
参照）AtCoderでダイクストラ法を使う最初に出た問題！？AtCoder Beginner Contest 035 [D - トレジャーハント]をScipyのdijkstraで解く（正解率21.51%） - 人工知能と競プロやってくブログ
ロジックの考え方は以下の動画を参考にしました。(こちらもよく紹介されていたので有名？)グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube
という訳で以下、解説 ありきで実装してみます。
test_dataABC035D = [
{
"in":"""2 2 5
1 3
1 2 2
2 1 1
""",
"out": """6
"""
},{
"in":"""2 2 3
1 3
1 2 2
2 1 1
""",
"out": """3
"""
},{
"in":"""8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30
""",
"out": """1488
"""
},
]
def ABC035D():
from collections import defaultdict
import heapq as hq
N, M, T = map(int, input().split())
*A, = map(int, input().split())
edge = defaultdict(list)
edge_rev= defaultdict(list)
for _ in range(M):
a, b, c = map(int, input().split())
edge[a].append((b, c))
edge_rev[b].append((a, c))
def dijkstra(n, e, start, goal=None):
# cost = defaultdict(lambda: float("inf"), {start: 0})
# 1-indexed
cost = [float('inf')] * (n + 1); cost[start] = 0
q = [(cost[start], start)]
fixed = set()
while q:
_, now = hq.heappop(q)
if now in fixed: continue
fixed.add(now)
if goal and now == goal: break
for nxt, c in e[now]:
if nxt in fixed: continue
cost[nxt] = min(cost[nxt], cost[now] + c)
hq.heappush(q, (cost[nxt], nxt))
return cost
print(max([
A[i] * (T - (a + b))
for i, (a, b) in
enumerate(zip(
dijkstra(N, edge, 1)[1:],
dijkstra(N, edge_rev, 1)[1:]
))
if a + b < T
]))
for data in test_dataABC035D:
test(ABC035D, data)
結果：#40698295
なんとなくダイクストラ法理解できました😊
まぁ武器が一つ増えたということで、よし！
自由欄
自由欄
AtCoder Inc.
