[ABC422] ABC 422(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- マリオをイメージして条件分岐するか。
- というか、
stageが最後かどうかだけ見て、エラーハンドリングしなくてよくね？（）（）（）
A.py
"""
<方針>
- マリオをイメージして条件分岐するか。
- というか、`stage` が最後かどうかだけ見て、エラーハンドリングしなくてよくね？（）（）（）
"""
# 入力
S = input()
# 情報抽出
world = int(S[0])
stage = int(S[2])
# 次のステージへ
if(stage == 8):
stage = 1
world += 1
else:
stage += 1
# 出力
print(str(world) + "-" + str(stage))
B問題
- 虱潰しで行くか。
B.py
"""
<方針>
- 虱潰しで行くか。
"""
# 入力
H, W = map(int, input().split())
SS = [input() for _ in range(H)]
# 全部2or4個の黒と隣接しているかどうか
ok = True
# 虱潰し
for i in range(H):
for j in range(W):
# 自分が黒の場合
if(SS[i][j] == "#"):
# 黒と隣接した数をカウント
cnt = 0
# 上下左右
for dy, dx in [
(+1, 0),
(-1, 0),
(0, +1),
(0, -1),
]:
# 上下左右を取得
k = i + dy
l = j + dx
# 範囲内かどうか
if(
(0 <= k < H) and
(0 <= l < W)
):
# 黒かどうか
if(SS[k][l] == "#"):
cnt += 1
# 隣接した黒の個数が2個か4個じゃない場合
if(cnt not in [2, 4]):
ok = False
break
# 出力
print("Yes" if ok else "No")
C問題
方針
- テストケースの線形時間でちょうどくらいで、文字の個数は線形すら許されない。
- となると、各テストケースを数学的に定数時間で求める必要がある。
- まず、
"A"と"C"の個数が第１のボトルネックになる。 - あと、第２のボトルネックとして、文字を全て使えたとしても、コンテスト一回あたり文字を３つ消費するため、開催できるコンテストは文字の個数の三分の一になる。
- まず、
- 全体として、
O(T)になる。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- テストケースの線形時間でちょうどくらいで、文字の個数は線形すら許されない。
- となると、各テストケースを数学的に定数時間で求める必要がある。
- まず、`"A"` と `"C"` の個数が第１のボトルネックになる。
- あと、第２のボトルネックとして、。
- 全体として、`O(T)` になる。
"""
T = int(input())
for _ in range(T):
# テストケース
nA, nB, nC = map(int, input().split())
# 第１のボトルネック
neck1 = min(nA, nC)
# 第２のボトルネック
neck2 = (nA+nB+nC)//3
# コンテスト開催可能回数
ans = min(neck1, neck2)
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．