[ABC410] ABC 410(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
-
filter関数使ってみるか。
A.py
"""
<方針>
- `filter` 関数使ってみるか。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
K = int(input())
print(len(list(filter(lambda x: K<=x, A))))
B問題
- 言われた通りにやる。
B.py
"""
<方針>
- 言われた通りにやる。
"""
# 入力
N, Q = map(int, input().split())
X = list(map(int, input().split()))
# ボックス
B = [0]*N
ans = []
# 順番に見る
for x in X:
# 一番少ないやつにボール入れる。
if(x == 0):
bMin = min(B)
for i in range(N):
if(B[i] == bMin):
B[i] += 1
ans.append(i+1)
break
# 特定のやつにボール入れる。
else:
B[x-1] += 1
ans.append(x)
# 出力
print(*ans)
C問題
方針
- タイプ３のクエリを愚直に処理するのは絶対に許されない。そもそも
k<=10**9だし。 - 何回「先頭の要素を末尾に移動したか」の変数
Kさえ保持して、あとはよしなに処理を行えば、整数列生成を含めて、O(N+Q)で行けるはず。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- タイプ３のクエリを愚直に処理するのは絶対に許されない。そもそも `k<=10**9` だし。
- 何回「先頭の要素を末尾に移動したか」の変数 `K` さえ保持して、あとはよしなに処理を行えば、整数列生成を含めて、`O(N+Q)` で行けるはず。
"""
# 入力
N, Q = map(int, input().split())
# 整数列の生成
A = list(range(1, N+1))
# 先頭の要素を末尾に移動したか
K = 0
# クエリ処理
for _ in range(Q):
match list(map(int, input().split())):
case [1, p, x]:
A[(p-1+K)%N] = x
case [2, p]:
print(A[(p-1+K)%N])
case [3, k]:
K += k
D問題
- 公式解説と一緒です。
- （
W <= 2**60かと勘違いしてた...）
D.py
"""
<方針>
- 公式解説と一緒です。
- （`W <= 2**60` かと勘違いしてた...）
"""
# 入力
N, M = map(int, input().split())
W = 2**10
E = [[[] for _ in range(W)] for _ in range(N)]
# グラフ構築
for _ in range(M):
a, b, a_b_w = list(map(int, input().split()))
a -= 1
b -= 1
# 全てのaのコストから、xorしたbへの辺を作成。
for w in range(W):
E[a][w].append([b, w^a_b_w])
# 到達したかどうか
visited = [[False]*W for _ in range(N)]
# DFS
q = [[0, 0]]
visited[0][0] = True
while q:
u, u_w = q.pop() # DFS
for v, v_w in E[u][u_w]:
if not visited[v][v_w]:
visited[v][v_w] = True
q.append([v, v_w])
# 最終到達点から、コストの小さい方から見る
for i, visit in enumerate(visited[-1]):
# 到達していれば、
if(visit):
# 出力
print(i)
exit()
# 到達不可能
print(-1)
E問題
-
dp[i][j] = mで解く。-
i: N番目の敵。0の時、試合開始前 -
j: 現在の体力 -
m: 現在の魔力
-
E.py
"""
<方針>
- `dp[i][j] = m` で解く。
- `i`: N番目の敵。0の時、試合開始前
- `j`: 現在の体力
- `m`: 現在の魔力
"""
N, H, M = map(int, input().split())
# dp[i][j] = m
## i: N番目の敵。0の時、試合開始前
## j: 現在の体力（HP）
## m: 現在の魔力（MJ）
dp = [[-1]*(H+1) for _ in range(N+1)]
# 最初は、HP=Hで、MJ=M
dp[0][H] = M
# dp遷移
for i in range(N):
a, b = map(int, input().split())
for j in range(H+1):
# HP攻撃
if(j >= a):
dp[i+1][j-a] = max(dp[i+1][j-a], dp[i][j])
# MJ攻撃
if(dp[i][j] >= b):
dp[i+1][j] = max(dp[i+1][j], dp[i][j] - b)
# 一番奥まで当樽したパターンを出力
for i in reversed(range(N+1)):
if(max(dp[i]) >= 0):
print(i)
break
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- あのジョセフに俺よりやばい的な事言わせたシュトロハイムってやっぱすげえよな。