AtCoder ABC404 振り返り(緑コーダーがPythonでABCD問題)

## AtCoder Beginner Contest 404 を振り返ります

[AtCoder Beginner Contest 404（Promotion for Engineer Guild） - AtCoder](https://atcoder.jp/contests/abc404)

今回はD問題まで4問解答でした。レーティングは久々に微増でした。
D問題は解けたんですけども、時間がかかってしまったのが反省です。深さ優先探索の実装がなかなかうまくできなかったので、こういう典型問題はさくっと解いてしまいたいところです。
また、B問題で単純ミスで、一回WAしてしまったのが痛かったかもです。

## A - Not Found
[A - Not Found](https://atcoder.jp/contests/abc404/tasks/abc404_a)

アルファベットの26文字分の配列を用意します。 ``` "a","b","c","d"... ``` と探していって、文字列Sに含まれなかった文字を出力すればOKです。


``` python
S = list(input())
char_list = list(string.ascii_lowercase) # "a","b","c","d"... の配列

# "a" から順に、含まれない文字を探す
for i in range(len(char_list)):
    if char_list[i] not in S:
        print(char_list[i])
        break
```

## B - Grid Rotation 
[B - Grid Rotation](https://atcoder.jp/contests/abc404/tasks/abc404_b)

B問題としては難しかったような...。グリッドの大きさが 100以下ですので、全探索をします。

Sが90度右回転できるので、以下のパターンを求めて、操作回数が最小になるものを求めれば良いです。

* S, Tをそのまま比較し、色が異なる箇所をカウント
* S(90度回転), Tを比較し、色が異なる箇所をカウント
* S(180度回転), Tを比較し、色が異なる箇所をカウント
* S(270度回転), Tを比較し、色が異なる箇所をカウント


以下の2つのメソッドを用意しておけば楽になります。
* グリッド中で、色が異なる箇所をカウントするメソッド
* グリッドを右回転させるメソッド

:::note warn
本番では270度回転を書き忘れて、WAになりました...
:::

``` python
N = int(input())
S = []
T = []
for i in range(N):
    s = input()
    S.append(s)
for i in range(N):
    t = input()
    T.append(t)

# 配列 s, t の中で、色が異なる箇所をカウントする
def count(s, t):
    count = 0
    for i in range(N):
        for j in range(N):
            if s[i][j] != t[i][j]:
                count += 1
    return count

# グリッドを右回転させる
def rotate_right(s):
    new_s = []
    for i in range(N):
        line = []
        for j in range(N):
            line.append(s[N - j - 1][i])
        new_s.append(line)
    return new_s

#［回転なし、90回転, 180回転, 270回転]の中で最小値を求める
answer = INF
answer = min(answer, count(S, T))
answer = min(answer, count(rotate_right(S), T) + 1)
answer = min(answer, count(rotate_right(rotate_right(S)), T) + 2)
answer = min(answer, count(rotate_right(rotate_right(rotate_right(S))), T) + 3)
print(answer)
```

## C - Cycle Graph? 

[C - Cycle Graph?](https://atcoder.jp/contests/abc404/tasks/abc404_c)

以下のように求めれば、答えが出ると考えて実装しました。

```
[1] # 1から始める
[1, 3] # 1から行ける頂点は[3,4] なので、3を追加
[1, 3, 2] # 3から行ける頂点は[1,2] なので、2を追加 (1は追加済み)
[1, 3, 2, 4] # 2から行ける頂点は[3,4] なので、4を追加 (3は追加済み)
先頭と末尾をつなぐ辺があれば、サイクルグラフ=Yes。なければ=No.
```

追加済判定を楽にするため、追加済頂点を set で管理します。
あと、サイクルグラフなら、頂点から伸びる辺はかならず2つになるので、そこもチェックするようにしました。


``` python
N, M = map(int, input().split())
path = defaultdict(set)
for i in range(M):
    a, b = map(int, input().split())
    path[a].add(b)
    path[b].add(a)

used_set = set() # 使用済頂点を管理するSet
queue = deque()  # サイクルグラフをdequeで管理

# 頂点1から始める
queue.append(1)
used_set.add(1)

is_loop = True
while True:
    current = queue[-1]
    next_set = path[current]

    # ある頂点から行ける頂点は2つ
    if len(next_set) != 2:
        is_loop = False
        break

    # 次の頂点に行けなくなったら、ループ終了
    exist = False
    for next in next_set:
        # 次に行ける頂点があれば、ループ続行
        if next not in used_set:
            exist = True
            queue.append(next)
            used_set.add(next)
            break

    if exist == False:
        break

if is_loop == False:
    print("No")
    exit()

# キューの中にN頂点が入っていて、最初と最後をつなぐパスがあればYes
if len(queue) == N:
    first = queue[0]
    last = queue[-1]
    if first in path[last]:
        print("Yes")
        exit()

print("No")
```


## D - Goin' to the Zoo
[D - Goin' to the Zoo](https://atcoder.jp/contests/abc404/tasks/abc404_d)

データの持ち方を変えて、動物園になんの動物がいるかを考えます。

```
# 入力例 1 の場合
zoo 1 = [1, 1, 1] (動物1,2,3がいる)
zoo 2 = [0, 1, 0] (動物2がいる)
zoo 3 = [1, 0, 1] (動物1,3がいる)
zoo 4 = [1, 1, 0] (動物1,2がいる)
```


あとは、それぞれの動物園を0回〜2回見た場合のパターンを全探索しまして...

```
Zoo1 を (0回 or 1回 or 2回)見た
Zoo2 を (0回 or 1回 or 2回)見た
Zoo3 を (0回 or 1回 or 2回)見た
...
Zoo10 を (0回 or 1回 or 2回)見た
```

最終的に、全動物を2回以上見ていればokです。
計算量は　3**10=59049 なので、十分間に合いそうです。

----

全探索には深さ優先探索を使用しました。



``` python
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 18

N, M = map(int, input().split())
C = list(map(int, input().split()))
C.insert(0, 0)

# 動物園ごとに、いる動物の配列
zoo = [[0] * (M) for _ in range(N + 1)]

for i in range(M):
    KA = list(map(int, input().split()))
    for j in range(1, len(KA)):
        zoo[KA[j]][i] = 1

min_cost = INF # コストの最小値
current_saw = [0] * (M) # 動物を見た回数を記録する配列

# 深さ優先探索
def dfs(zoo_index, current_cost):
    global min_cost

    # 動物園を見終わって、すべての動物を2回以上見ていればok
    if zoo_index == N:
        if min(current_saw) >= 2:
            min_cost = min(min_cost, current_cost)           
        return

    # 次の動物園を(0回 or 1回 or 2回)見るパターンを探索
    next_zoo = zoo[zoo_index+1]
    for next_visit_count in range(0, 3):
        for i in range(M ):
            current_saw[i] += next_zoo[i] * next_visit_count
        dfs(zoo_index + 1, current_cost + C[zoo_index + 1] * next_visit_count)
        for i in range(M ):
            current_saw[i] -= next_zoo[i] * next_visit_count

# 探索開始
dfs(0, 0)

print(min_cost)
```