[ABC450] ABC 450(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
-
joinを使おう．
A.py
"""
<方針>
- `join` を使おう．
"""
# 入力
N = int(input())
# 連続数字を作成
con = [str(N-i) for i in range(N)]
# 文字列をjoinで生成
ans = ",".join(con)
# 出力
print(ans)
B問題
- 総当たりをする．
B.py
"""
<方針>
- 総当たりをする．
"""
# 入力
N = int(input())
CC = [[None]*(i+1) + list(map(int, input().split())) for i in range(N-1)]
# 総当たり
for a in range(N):
for b in range(N):
for c in range(N):
if(a < b < c):
if(CC[a][b] + CC[b][c] < CC[a][c]):
print("Yes")
exit()
# 見つからなかったら
print("No")
C問題
方針
-
O(HW)程度で終わるように頑張ろう． - dfs 等で領域を上下左右が繋がってる領域を黒くしていく．
- まとめた領域の数をカウントする．
- ただし，端っこに面してる領域はカウントしない．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `O(HW)` 程度で終わるように頑張ろう．
- dfs 等で領域を上下左右が繋がってる領域を黒くしていく．
- まとめた領域の数をカウントする．
- ただし，端っこに面してる領域はカウントしない．
"""
H, W = map(int, input().split())
SS = [list(input()) for _ in range(H)]
ans = 0
# 全てのマスをみる．
for i in range(H):
for j in range(W):
# 白かったら
if(SS[i][j] == "."):
is_edge = False # 端っこフラグ
q = [
[i, j]
]
while q:
# dfs
h, w = q.pop()
# 端っこ判定
if((h in [0, H-1]) or (w in [0, W-1])):
is_edge = True
# 黒く塗る
SS[h][w] = "#"
# 上下左右を見る
for dh, dw in [
(+1, +0),
(+0, +1),
(-1, +0),
(+0, -1),
]:
hh = h+dh
ww = w+dw
if((0 <= hh < H) and (0 <= ww < W)):
if(SS[hh][ww] == "."):
# 白ければ，キューに入れる．
q.append([hh, ww])
# 端っこに面していなければ，条件を満たすので追加する．
if(not is_edge):
ans += 1
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- おいこんこんさむらい