[ABC415] ABC 415(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
-
inを使って簡単に判定しよう。
A.py
"""
<方針>
- `in` を使って簡単に判定しよう。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
X = int(input())
# 存在判定
if(X in A):
print("Yes")
else:
print("No")
B問題
- ２個ずつ荷物
#を取り出していき、取り出したところには、.を入れておこう。
B.py
"""
<方針>
- ２個ずつ荷物 `#` を取り出していき、取り出したところには、`.` を入れておこう。
"""
# 値を変更できるように `list` で受け取る。
S = list(input())
# 倉庫に荷物があるかぎり
while "#" in S:
# 荷物の位置
places = []
# 倉庫を手前から見ていく。
for i, s in enumerate(S):
# 荷物が見つかったら
if(s == "#"):
# 荷物の位置を登録する
places.append(str(i+1))
# 荷物を取り除く
S[i] = "."
# 荷物が２つ見つかったら、
if(len(places) == 2):
# 位置を出力して終了
print(",".join(places))
break
C問題
方針
- 混ぜられる薬のパターンをグラフの頂点
Vとして、置いておく。 - あらかじめ混ぜてはいけないパターンを登録しておく。
- あとは、薬を順番に混ぜていき、全部混ぜるパターンが実現できるかどうかをチェックすれば良い。
- 全パターン
2**Nと遷移Nで、O(2^N*N)なので間に合いそう。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 混ぜられる薬のパターンをグラフの頂点 `V` として、置いておく。
- あらかじめ混ぜてはいけないパターンを登録しておく。
- あとは、薬を順番に混ぜていき、全部混ぜるパターンが実現できるかどうかをチェックすれば良い。
- 全パターン `2**N` と遷移 `N` で、`O(2^N*N)` なので間に合いそう。
"""
T = int(input())
for _ in range(T):
# 入力
N = int(input())
S = input()
# 薬を混ぜるパターン
## 0: 未知
## 1: 安全
## 2: 危険
V = [0]*(2**N)
# 危険を登録
for i, s in enumerate(S):
if(s == "1"):
V[i+1] = -1
# 何も混ぜていないのは安全
V[0] = 1
# 下から順番に見ていく
for i in range(2**N):
# 安全であれば、
if(V[i] == 1):
# 遷移を考える。
for j in range(N):
# 薬品jををまだ混ぜていなければ、
if((i >> j) & 1 == 0):
nex = i + 2**j
# 危険でなければ、
if(V[nex] != -1):
V[nex] = 1
# 全部混ぜたパターンが安全かどうか
if(V[-1] == 1):
print("Yes")
else:
print("No")
D問題
- 貪欲にいけば良さそう。瓶の減少が一番小さいやつを選んでいく。
- ただし、
Nがデカすぎるので、そこは解析的に求める必要がある。
D.py
"""
<方針>
- 貪欲にいけば良さそう。瓶の減少が一番小さいやつを選んでいく。
- ただし、`N` がデカすぎるので、そこは解析的に求める必要がある。
"""
# 入力
N, M = map(int, input().split())
AB = []
for _ in range(M):
a, b = map(int, input().split())
AB.append([a, b])
# 瓶の減少がが小さい順にsort
AB.sort(key=lambda x: x[0]-x[1])
# 貪欲に進める
ans = 0
for a, b in AB:
# １回以上交換できる時、
if(N>=a):
# ギリギリまで交換する。
cnt = (N-a)//(a-b)+1
# 瓶の数を減らす
N -= cnt*(a-b)
# 答えに追記する。
ans += cnt
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- できるわけがない！！