ABC297の振り返り(Eとダイクストラ法)

振り返りです。

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 - Kth Takoyaki Set

やってみよう！

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してしまった…
こんなシンプルに解けたとなると、どこか穴がないか不安になります…

自由欄

ダイクストラ法

これまで名前は見てきたものの、ずっと後回しにしていたダイクストラ法をしっかり理解してみます。
(初見は約9ヶ月前の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

なんとなくダイクストラ法理解できました😊
ただ、これを知っていたからと言って今回のE問題が解けたかどうか…

まぁ武器が一つ増えたということで、よし！

自由欄