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

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

# A問題
- 文字を一つずつ見て， `A` `B` `C` が全て存在していれば，並び替えれば `ABC` になると言える．
```A.py
"""
<方針>
- 文字を一つずつ見て， `A` `B` `C` が全て存在していれば，並び替えれば `ABC` になると言える．
"""
# 入力
S = input()

# それぞれの文字が存在したかを記録するフラグ
a_exist = False
b_exist = False
c_exist = False

# 全ての文字を見る
for s in S:
  # Aだった
  if s == "A":
    a_exist = True
  # Bだった
  if s == "B":
    b_exist = True
  # Cだった
  if s == "C":
    c_exist = True

# 全部存在してたら
if a_exist and b_exist and c_exist:
  # 並び替えてABCになる
  print("Yes")
# そうでなければ
else:
  # 不可能
  print("No")
```

# B問題
- どこにコマを置くことができるかの変数 `ok` を作る．最初は `True` のリストで初期化しておく．
- 入力を受け取り，ルーク `#` があったら，それが移動できる場所を `ok` 上で `False` にする．
- 最後まで残った `ok` 上の `True` をカウントすればいける．
```B.py
"""
<方針>
- どこにコマを置くことができるかの変数 `ok` を作る．最初は `True` のリストで初期化しておく．
- 入力を受け取り，ルーク `#` があったら，それが移動できる場所を `ok` 上で `False` にする．
- 最後まで残った `ok` 上の `True` をカウントすればいける．
"""
# 盤面の大きさ
N = 8
# 駒がおける場所
ok = [[True]*N for i in range(N)]

# 入力を受け取る
for i in range(N):
  # 入力
  S = input()
  for j, s in enumerate(S):
    # ルークがあったとき
    if s == "#":
      # 横方向の更新
      for ind in range(N):
        ok[i][ind] = False
      # 縦方向の更新
      for ind in range(N):
        ok[ind][j] = False

# おける場所をカウント
ans = 0
for i in range(N):
  for j in range(N):
    if ok[i][j]:
      ans += 1

# 出力
print(ans)
```

# C問題
## 方針

- B問題と同じように盤面を作るところから始めると， `N` がデカすぎるため， `O(N^2)` はとても間に合わない．
- 盤面は作らずとも，ナイトの可動域を登録すれば十分である．
- 重複の無いように，全てのナイトの可動域を登録すれば良い．
- `set` を使うと，重複の無い追加が `O(1)` でできる．
- 高々 `M` 個のクイーンで前述の処理をするので， `O(M)` により間に合う．
- テクニック
  - `0-indexed` でやる
  - ナイトの可動域はリストを作成して， `for` でまとめてやる
  - `set` の値は `int` にするため，縦横のいずれかの値を `N` 倍すると上手くいく．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- B問題と同じように盤面を作るところから始めると， `N` がデカすぎるため， `O(N^2)` はとても間に合わない．
- 盤面は作らずとも，ナイトの可動域を登録すれば十分である．
- 重複の無いように，全てのナイトの可動域を登録すれば良い．
- `set` を使うと，重複の無い追加が `O(1)` でできる．
- 高々 `M` 個のクイーンで前述の処理をするので， `O(M)` により間に合う．
- テクニック
  - `0-indexed` でやる
  - ナイトの可動域はリストを作成して， `for` でまとめてやる
  - `set` の値は `int` にするため，縦横のいずれかの値を `N` 倍すると上手くいく．
"""
# 入力
N, M = map(int, input().split())

# ナイトの可動域
se = set()

# 全てのナイトを処理する
for i in range(M):
  # 入力
  a, b = map(int, input().split())
  # 0-indexed
  a, b = a-1, b-1
  # ナイトの可動域を全て確認する
  for x, y in [
    (0, 0),
    (1, 2), 
    (1, -2), 
    (-1, 2), 
    (-1, -2), 
    (2, 1), 
    (2, -1), 
    (-2, 1),
    (-2, -1), 
    ]:
      # ナイトの移動先
      A = a + x
      B = b + y
      # ナイトの移動先が盤面の中のとき
      if(0<=A<N and 0<=B<N):
        # 縦方向の値をN倍したものをナイトの可動域に追加する．(setへの追加なので，重複の無い追加)
        se.add(A*N + B)
# 盤面の全体の広さから，ナイトの可動域を引くと答え．(len(se)はO(M)の処理)
print(N**2 - len(se))
```


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