【AtCoder】ABC232をPython3で解説（ABCD）

ABC232のA-D問題の解説。

https://atcoder.jp/contests/abc232

## 目次
[A - QQ solver](#a---qq-solver)
[B - Caesar Cipher](#b---caesar-cipher)
[C - Graph Isomorphism](#c---graph-isomorphism)
[D - Weak Takahashi](#d---weak-takahashi)

## A - QQ solver

https://atcoder.jp/contests/abc232/tasks/abc232_a

### 解説

文字列`S`は、`axb`という形になっており、これの$a \times b$を求める問題。

`a`と`b`を文字列からインデックスを指定して、整数型`int()`にしてから、かけ合わせれば`AC`。

### コード
```python
s = input()

a = int(s[0])
b = int(s[2])

print(a*b)
```
## B - Caesar Cipher

https://atcoder.jp/contests/abc232/tasks/abc232_b

### 解説

文字列`S`をアルファベット順に1文字ずつ動かしたとき、`S`は`T`に一致するかを求める問題。

pythonでは、アルファベットは`ord()`を用いると数値化できる。`ord('a')`は`97`、`ord('z')`は`122`である。

今回の問題は、`S`と`T`、それぞれの文字の距離がすべて等しいかを求めれば良い。

入力例1でいうと、`a`と`i`の距離は、$9 - 1 = 8$、`b`,`j`と`c`,`k`も等しく$8$である。したがって、すべての距離が等しいので`Yes`を出力する。

では、文字が折り返す`z`, `a`のときはどうだろう。$97 - 122 = -25$でこれでは距離が正しくない。このようなときに対して、$26$を足して、$26$で割ったあまりを出してあげれば、正しい距離である$1$が出力される。

あとは、すべての文字に対して行えばいいので、`set()`を利用して重複をなくし、`set()`の要素が1つであれば、`Yes`を出力してあげればよい。

![code.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/f0733d1b-0746-9722-7079-027251598e53.jpeg)


### コード
```python
s = list(input())
t = list(input())

st = set()

for i in range(len(s)):
    k = (ord(t[i])-ord(s[i])+26)%26
    st.add(k)

if len(st) == 1:
    print('Yes')
else:
    print('No')

```
## C - Graph Isomorphism

https://atcoder.jp/contests/abc232/tasks/abc232_c

### 解説

`A`と`B`、`C`と`D`のボールを、それぞれひもで結ぶおもちゃが2つある。おもちゃのボールに書かれている数を入れ替えてもよいとき、それぞれのおもちゃの形は等しいかどうかを求める問題。

おもちゃの形が等しいかどうかは、各ボール同士をつなぐひもが、各おもちゃで等しければよい。
したがって、ボールの番号を振りかえる、`N!（N*N-1*...*1）`とおり試せば良い。

これを管理するには、**隣接リスト**を用いる。
ひもで繋がれている各ボールをリストのインデックス番号に追加する。その後、`N!`通りに対して、全ボールの組み合わせを考える。隣接リストの各要素は、`0`か`1`に限定されるので、すべてのひもの組み合わせが2つのおもちゃにおいて等しければ、`flag`は立ったままなので、`Yes`を出力してあげれば良い。

![code 2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/d86f0c7b-8792-5eab-4b18-d85ae8fdd1fc.jpeg)


### コード
```python
from itertools import permutations

n, m = map(int, input().split())
ga = [[0]*n for _ in range(n)]
gb = [[0]*n for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    ga[u][v] = ga[v][u] = 1

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    gb[u][v] = gb[v][u] = 1

ans = False

for p in permutations(range(n)):
    flag = True
    for i in range(n):
        for j in range(n):
            if ga[i][j] != gb[p[i]][p[j]]:
                flag = False
    if flag:
        ans = True
        break 

if ans:
    print('Yes')
else:
    print('No')
```
## D - Weak Takahashi

https://atcoder.jp/contests/abc232/tasks/abc232_d

### 解説
`H`$\times$`W`のグリッドがあり、マス$(i, j)$にいるとき、マス$(i+1, j)$かマス$(i, j+1)$に動くことができるとする。マス$(1, 1)$にいるとき、最大で移動できるマスの数を答える問題。

結論から言うと、DPを利用して問題を解く。
DPについて詳しく知りたい方は、アルゴ式を参考にしていただきたい。

https://algo-method.com/lecture_groups/7

DPとは、「問題全体を部分問題に分解し、各部分問題に対する解をメモしながら、小さな部分問題からより大きな部分問題へと順に解を求めていく手法」である。主に、この問題では、メモを右下から行っていく。

今回の問題では、右か下にしか進むことができないので、メモの仕方としては、`max(dp[i][j], dp[i+1][j]+1)`、`max(dp[i][j], dp[i][j+1]+1)`となる。
これを右下から左上にかけて、各行各列に対して行っていくことで、すべてのマスに対して最大の移動距離を求めることができる。

このとき、マス$(1, 1)$からの最大移動距離なので、`dp[0][0]`を出力させれば、`AC`である。

![IMG_1056.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/60e68924-23e1-03f8-f8b0-be057da936d3.jpeg)


![code 1.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/6a2612c2-7049-9401-296e-57d7f9d134c5.jpeg)


### コード
```python
h, w = map(int, input().split())

s = [list(input()) for _ in range(h)]

dp = [[0]*w for _ in range(h)]

for i in range(h-1, -1, -1):
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            continue
        dp[i][j] = 1
        if i+1 < h:
            dp[i][j] = max(dp[i][j], dp[i+1][j]+1)
        if j+1 < w:
            dp[i][j] = max(dp[i][j], dp[i][j+1]+1)

print(dp[0][0]) 
```

## 編集後記

授業でやったDPが理解できるようになったのが嬉しい。
DPまとめとかやろうかな。