ABC 302 備忘録

## 概要
　今回はABC 302（2023年5月20日21:00~22:40）についてポイントと自分の実装、および感想について述べていこうと思う。
## A問題
https://atcoder.jp/contests/abc302/tasks/abc302_a

### ポイント
- `A` が `B` で割り切れる場合にはその商を出力
- それ以外の場合には、商の値 `+1` の値を出力

### 自分の実装
```Python:ABC_302_A.py
A, B = map(int, input().split())

if A%B == 0:
    print(A//B)
else:
    print(A//B + 1)
```
## B問題
https://atcoder.jp/contests/abc302/tasks/abc302_b

### ポイント
- 縦・横・斜めの8方向についてのグリッド操作をまとめて用意しておく
- マス目内で始点となる `s` にあたる部分を全探索し、ある1方向に対して一気に5文字が条件に合致するかどうかを判断
- 全探索中に元々のマス目を飛び出さないように注意

### 自分の実装
```Python:ABC_302_B.py
H, W =  map(int, input().split())

# マス目の入力
S = list(input() for i in range(H))

# 動く方向の組み合わせ
vertical = [0, 1, 1, 1, 0, -1, -1, -1]
horizontal = [1, 1, 0, -1, -1, -1, 0, 1]

for i in range(H):
    for j in range(W):
        for k in range(8):
            if i + 4 * vertical[k] <= H-1 and i + 4 * vertical[k] >= 0 and j + 4 * horizontal[k] <= W-1 and j + 4 * horizontal[k] >= 0:
                ver_k, hor_k = vertical[k], horizontal[k]
                if S[i][j] == 's' and S[i + ver_k][j + hor_k] == 'n' and S[i + 2 * ver_k][j + 2 * hor_k] == 'u' and S[i + 3 * ver_k][j + 3 * hor_k] == 'k' and S[i + 4 * ver_k][j + 4 * hor_k] == 'e':
                    print(i+1, j+1)
                    print(i+ver_k+1, j+hor_k+1)
                    print(i+2*ver_k+1, j+2*hor_k+1)
                    print(i+3*ver_k+1, j+3*hor_k+1)
                    print(i+4*ver_k+1, j+4*hor_k+1) 
                    exit()
```

## C問題
https://atcoder.jp/contests/abc302/tasks/abc302_c

### ポイント
- `Python` の `itertools` というライブラリを用いて、`0 ~ N-1` の順列を出力
- 出力した順番に文字列の順番を並び替えて、前後の文字の相違している数をカウント

### 自分の実装
```Python:ABC_302_C.py
import itertools

N, M = map(int, input().split())

# 文字列の入力
S = list(input() for i in range(N))

# 比較する数列番号の順列の取得
permutation_lists = list(itertools.permutations(range(N), N))

# 並び替えた文字列の保存
T = ["" for i in range(N)]
ans = "No"

for lists in permutation_lists:
    # 文字列の並び替え
    for i in range(N):
        T[i] = S[lists[i]]
        if i >= 1:
            dif = 0
            for j in range(M):
                if T[i][j] != T[i-1][j]:
                    dif += 1
            if dif != 1:
                break
        if i == N-1:
            print("Yes")
            exit()
            
print("No")
```

## D問題
https://atcoder.jp/contests/abc302/tasks/abc302_d

### ポイント
- プレゼントの価値の順番でそれぞれソート
- 価値の大きいものから（後ろの要素から）取り出して価値の差の絶対値を評価
- 絶対値が`D`以下ならばそれが最大の和なので終了
- どちらかのプレゼントの候補が完全に無くなった場合でも終了

### 自分の実装
```Python:ABC_302_D.py
from collections import deque as d

N, M, D = map(int, input().split())

A = d(sorted(list(map(int, input().split()))))
B = d(sorted(list(map(int, input().split()))))

ans = -1
A_max = A.pop()
B_max = B.pop()

while True:
    if abs(A_max - B_max) <= D:
        ans = A_max + B_max
        break
    elif A_max > B_max:
        if len(A) >= 1:
            A_max = A.pop()
        else:
            break
    elif A_max < B_max:
        if len(B) >= 1:
            B_max = B.pop()
        else:
            break
print(ans)
```

## 感想
　時間内に解けたのは、A~C問題までで、D問題で`TLE`を連発してしまった。計算量的に全ての要素について比較するのは、`TLE`になるとはわかっていても実が時間中に思い浮かばなかった。

　公式の解説を読んで実装をやり直したらできた。コンテスト当時は、全てのプレゼントの差を考える必要があるので`numpy`で一気に差を考えようとしていたのだが、最大の値からどんどん下げていけば計算量的に時間内に収まるのだと分かった（2023年5月30日追記）。