[ABC391] ABC 391(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)

# [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回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`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)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc391)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc391/submissions/62463517)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc391/submissions/62463665)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc391/submissions/62463885)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 忙しさが極まってるので，ABCだけにします．
- あ．僕鳩好きです．
- おすすめのハト置いときます．

https://manga.nicovideo.jp/comic/43196

<iframe width="1280" height="720" src="https://www.youtube.com/embed/JQVKkjA0law" title="田舎でよく聞く鳥の鳴き声をEDMにしました(ハトの鳴き声)(キジバト)" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>