【ABC317】AtCoder Beginner Contest 317 A-D 振り返り【Python】

https://atcoder.jp/contests/abc317

A - Potions

以下の条件になるまで傷口を順番に選択する。
$P_n$ (傷薬nの回復量) + $H$ (現在の体力) $\geq$ $X$ (目標体力)

N, H, X = map(int, input().split())
p_list = list(map(int, input().split()))

for i, p in enumerate(p_list):
    if H + p >= X:
        print(i + 1)
        exit()

B - MissingNo.

ナオヒロ君が持っている整数の最小値から最大値まで順番に持っているかどうかを確認する。
所持しているかどうかの判定をするために所持している整数をset()にすると計算量が減る。

n = int(input())
a_list = list(map(int, input().split()))
a_set = set(a_list)

for i in range(min(a_set), max(a_set)):
    if not i in a_set:
        print(i)
        exit()

C - Remembering the Days

ほとんど公式解説と同じ。街の個数が$N$個なので優先探索で計算時間を考慮しても間に合う。

n, m = map(int, input().split())

graph = [[0] * (n) for _ in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

ans = 0
passed = [False] * n  # 通った道を記録する

def dfs(v, cost):  # vが現在地点, costが現在のコスト
    global ans
    passed[v] = True
    if cost > ans:  # 最大コストだったら回答を更新
        ans = cost
    for i in range(n):
        if not passed[i] and graph[v][i] != 0:
            dfs(i, cost + graph[v][i])
    passed[v] = False

for i in range(n):
    dfs(i, 0)

print(ans)

D - President

公式の解説にある通り、ナップサック問題のようにdpを作成して問題を解く。
$dp[n]$ : n議席得るのに必要な寝返りの人数
思考過程は以下の通り (入力例4を使用)