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

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

# A問題
- `set` に `S` の文字を一つずつ登録する。
- `ord` と `chr` を使ってアルファベットを数字から手に入れる。
- `in` を使って存在判定をする。
```A.py
"""
<方針>
- `set` に `S` の文字を一つずつ登録する。
- `ord` と `chr` を使ってアルファベットを数字から手に入れる。
- `in` を使って存在判定をする。
"""
# 入力
S = input()

# set
se = set()
for s in S:
  se.add(s)

# アルファベット生成
alphabets = []
for i in range(26):
  alphabet = chr(i + ord("a"))
  alphabets.append(alphabet)

# 存在判定
for alphabet in alphabets:
  # setになければ、
  if not (alphabet in se):
    # 出力
    print(alphabet)
    # プログラム終了
    exit()
```

# B問題
- 先に回転する。
  - 回転のパターンは `0 90 180 270` の `4` パターンのみ。
  - 回転の方法は `*` と `zip` を使って行う。
- 回転させた後に、黒と白が異なるところを反転させる。
```B.py
"""
<方針>
- 先に回転する。
  - 回転のパターンは `0 90 180 270` の `4` パターンのみ。
  - 回転の方法は `*` と `zip` を使って行う。
- 回転させた後に、黒と白が異なるところを反転させる。
"""
# 入力
N = int(input())
SS = [list(input()) for _ in range(N)]
TT = [list(input()) for _ in range(N)]

# 引数の違うところをカウントする関数
def count_diff(SS, TT):
  ans = 0
  for i in range(N):
    for j in range(N):
      if(SS[i][j] != TT[i][j]):
        ans += 1
  
  return ans


# 最適回数
ans = float("inf")
# 回転回数
for rot in range(4):
  # コピー
  new_SS = [S[:] for S in SS]
  # rot回、回転させる。
  for _ in range(rot):
    new_SS = list(zip(*reversed(new_SS)))
  
  # 回転させた分だけ操作カウント
  tmp = rot
  
  # 違うところをカウント
  tmp += count_diff(new_SS, TT)
  
  # 最適回数を更新
  ans = min(ans, tmp)

# 出力
print(ans)
```

# C問題
## 方針
- `N == M` であることをまず確かめる。
- それぞれの頂点を訪れたかどうかを探索で確認していき、訪れた頂点に達したら終了する。
- 全ての頂点を訪れており、最後に訪れた頂点が最初の頂点ならば、サイクルグラフ
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `N == M` であることをまず確かめる。
- それぞれの頂点を訪れたかどうかを探索で確認していき、訪れた頂点に達したら終了する。
- 全ての頂点を訪れており、最後に訪れた頂点が最初の頂点ならば、サイクルグラフ
"""
# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  
  E[A].append(B)
  E[B].append(A)
  

# 頂点と辺の数が合致するかどうかを確認する。
if(N != M):
  print("No")
  exit()

# 訪れたかどうか
visited = [False]*N

# キューに[前回訪れた頂点、今訪れている頂点]を入れる。
q = [[-1, 0]]

# DFS
while q:
  t, u = q.pop()
  
  # 訪れていれば終了する。
  if(visited[u]):
    last = u
    break
  
  # 訪れチェック
  visited[u] = True
  
  # 次の頂点を訪れる。
  for v in E[u]:
    # 前回の頂点は入れない。
    if(t != v):
      # 次の頂点を追加する。
      q.append([u, v])
  
# 全て訪れていて、最初の頂点に戻ってきたとき
if(all(visited) and last == 0):
  print("Yes")
else:
  print("No")
  
```

# D問題
- それぞれの動物園へ行くか行かないかの `bit` 探索を、`0` 回行く、 `1` 回行く、 `2` 回行くの `3` 進数探索をすれば良い。
```D.py
"""
<方針>
- それぞれの動物園へ行くか行かないかの `bit` 探索を、`0` 回行く、 `1` 回行く、 `2` 回行くの `3` 進数探索をすれば良い。
"""
# 入力を受け取る
N, M = map(int, input().split())
C = list(map(int, input().split()))
BB = [[] for _ in range(N)] # AAのindexを変えたもの。BB[動物園][動物]
for i in range(M):
  K, *A = map(int, input().split())
  for a in A:
    a -= 1
    BB[a].append(i)

# 3進数探索
ans = float("inf")
for i in range(3**N):
  # 動物を何回見たかどうか
  animals = [0]*M
  
  # かかったお金
  tmp = 0
  
  # それぞれの動物園を何回訪れたか
  for j in range(N):
    # moがj番目の動物園を訪れた回数
    i, mo = divmod(i, 3)
    # 訪れた動物園で見た動物の回数を登録する。
    for b in BB[j]:
      animals[b] += mo
    # 動物園に貢献した分を登録
    tmp += mo*C[j]
  
  # 全ての動物を2回以上見ていれば、
  if(all([a>=2 for a in animals])):
    ans = min(ans, tmp)

print(ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc404)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc404/submissions/65489447)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc404/submissions/65489678)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc404/submissions/65548311)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc404/submissions/65517943)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 可愛い後輩の力を借りて早起きに挑戦します。
- 確かピクミン3では地球っぽい星のことを `PNF-404` って呼んでた気がします。
- `C` 問題のソースコード一部間違ってました。ごめんね。