[ABC431] ABC 431(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 差分を出力すれば良い。
- マイナスにならないように、
maxを利用する。
A.py
"""
<方針>
- 差分を出力すれば良い。
- マイナスにならないように、`max` を利用する。
"""
# 入力
H, B = map(int, input().split())
# どれだけ頭が大きいか
ans = H - B
# マイナスにならないように調節
ans = max(ans, 0)
# 出力
print(ans)
B問題
- どの部品を取り付けたかを管理する変数
armsを使えば良さそう
B.py
"""
<方針>
- どの部品を取り付けたかを管理する変数 `arms` を使えば良さそう
"""
# 入力
X = int(input())
N = int(input())
W = list(map(int, input().split())) # 0-indexed
Q = int(input())
# どの部品を取り付けたかを管理する変数
arms = [False]*N # 0-indexed
# ループしてPを取得して、順次処理をする。
for _ in range(Q):
P = int(input())
P -= 1 # 0-indexed
# 取り外しor取り付けをして重さを変える
X += (-1 if arms[P] else +1)*W[P]
# 取り付けor取り外しを行う
arms[P] = not arms[P]
# 出力
print(X)
C問題
方針
- 全ての組み合わせするのは明らかに間に合わない
O(N!M!) - 小さい
Bは、なるべく小さいHだったら対応できるかも - その個数が
Kを超えるかを考えれば良い - この個数の列挙は、
O(N+M)で行けそう - だけど、最初にソートするから、そこで
O(NlogN+MlogM)になるけど、間に合いそう
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 全ての組み合わせするのは明らかに間に合わない `O(N!M!)`
- 小さい `B` は、なるべく小さい `H` だったら対応できるかも
- その個数が `K` を超えるかを考えれば良い
- この個数の列挙は、`O(N+M)` で行けそう
- だけど、最初にソートするから、そこで `O(NlogN+MlogM)` になるけど、間に合いそう
"""
# 入力
N, M, K = map(int, input().split())
H = list(map(int, input().split()))
B = list(map(int, input().split()))
# ソート
H.sort()
B.sort()
# ロボットが作れる個数
cnt = 0
# 今見てるHのインデックス
indH = 0
# Bから見ていく
for i in range(M):
h = H[indH]
b = B[i]
# ロボット作れそう
if(h<=b):
cnt += 1
indH += 1
# Hのパーツがもうない
if(indH == N):
break
# K個以上作れそうかどうか
if(cnt >= K):
print("Yes")
else:
print("No")
D問題
-
DPで解けそう-
key: 体の重さの方がどれだけ大きいか -
value: うれしさ
-
- 辞書で処理しないと間に合わなさそう
- あと、重い順番に入れていって、枝刈り的な効率化を図る
-
PyPyだとTLEするから、Codon使った...
D.py
"""
<方針>
- `DP` で解けそう
- `key`: 体の重さの方がどれだけ大きいか
- `value`: うれしさ
- 辞書で処理しないと間に合わなさそう
- あと、重い順番に入れていって、枝刈り的な効率化を図る
"""
N = int(input())
WHB = [list(map(int, input().split())) for _ in range(N)]
# 重さで降順にソート
WHB.sort(reverse=True)
# 残りの重さの累積和（後ろから）
S = [0]
for i in range(N - 1, -1, -1):
S.append(S[-1] + WHB[i][0])
# dp 初期化
dp = {0: 0}
# dp 遷移
for i in range(N):
W, H, B = WHB[i]
# 次のdpのベース
nx = dict()
# nxを構築する
for ke, va in dp.items():
nx[ke+W] = max(va + B, nx[ke+W] if(ke+W in nx) else 0) # Bにつける
# あとで復帰できるレベルなら、Hにつける
if (ke - W + S[N-i-1]) >= 0:
nx[ke-W] = max(va + H, nx[ke-W] if(ke-W in nx) else 0) # Hにつける
# 更新
dp = nx
print(max(dp.values()))
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- なえとる