[ABC391] ABC 391(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 方向1周分の
direction: listを作成する． - 反対方向は
-4したところになる．
A.py
"""
<方針>
- 方向1周分の `direction: list` を作成する．
- 反対方向は `-4` したところになる．
"""
# 入力
way = input()
# 方向を記録したlist
direction = [
"N",
"NE",
"E",
"SE",
"S",
"SW",
"W",
"NW",
]
# 入力の方向のindex
index_way = direction.index(way)
# 逆方向
ans = direction[index_way - 4]
# 出力
print(ans)
B問題
- ラスター走査する．
B.py
"""
<方針>
- ラスター走査する．
"""
# 入力
N, M = map(int, input().split())
SS = [list(input()) for _ in range(N)]
TT = [list(input()) for _ in range(M)]
# ラスター走査
for i in range(N-M+1):
for j in range(N-M+1):
# チェック
ng = False
for y in range(M):
for x in range(M):
if(SS[i+y][j+x] != TT[y][x]):
ng = True
# 全て同一であれば，
if(not ng):
a = i+1
b = j+1
print(a, b)
C問題
方針
- 毎ターン全ての鳩の巣を確認すると，
O(QN)かかってしまうためNG． - 入れ替わった鳩のだけに注目して，現在複数お鳩がいるのを保持すれば，
O(Q)の処理でいける． - 鳩を巣から一度出して，そこから鳩を他の巣に入れる処理に分割して考えると解きやすい．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 毎ターン全ての鳩の巣を確認すると，`O(QN)`かかってしまうためNG．
- 入れ替わった鳩のだけに注目して，現在複数お鳩がいるのを保持すれば，`O(Q)` の処理でいける．
- 鳩を巣から一度出して，そこから鳩を他の巣に入れる処理に分割して考えると解きやすい．
"""
# 入力
N, Q = map(int, input().split())
# それぞれの鳩がどこに住んでいるか
pigeons = list(range(N))
# それぞれの巣に何匹鳩がいるか
holes = [1]*N
# 現在複数の鳩が住んでいる巣の個数
cnt = 0
# シミュレーション
for _ in range(Q):
match list(map(int, input().split())):
# 鳩が移動するパターン
case [1, p, h]:
# 0-indexedにする
p -= 1
h -= 1
# 鳩が移動する前の場所
past = pigeons[p]
# 鳩を巣から出す
holes[past] -= 1
# その巣に住んでる匹数が1になった時，
if(holes[past]==1):
# 2->1 より，複数住んでる巣の数が減少した．
cnt -= 1
# 鳩を新しいところに移動させる．
new = pigeons[p] = h
# 鳩を巣に入れる．
holes[new] += 1
# その巣に住んでる引数が2になった時，
if(holes[new]==2):
# 1->2より，複数住んでる巣の数が増加した．
cnt += 1
# 複数の鳩が住んでる巣の個数を出力するパターン
case [2]:
# 出力
print(cnt)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 忙しさが極まってるので，ABCだけにします．
- あ．僕鳩好きです．
- おすすめのハト置いときます．