【Atcoder解法検討】ABC300 A~E Python

## A - N-choice question
#### 問題ページ : [A - N-choice question](https://atcoder.jp/contests/abc300/tasks/abc300_a)
### 考察 
$A+B=C_i$なる$i$が丁度1つ存在する、とのことなので$C_i$をリストで受け、頭から$A+B=C_i$となるiを探索すればOK.
### コード
```python
N, A, B = map(int, input().split())
C = list(map(int, input().split()))

for i in range(N):
    if A + B == C[i]:
        print(i+1)
```

## B - Same Map in the RPG World
#### 問題ページ : [B - Same Map in the RPG World](https://atcoder.jp/contests/abc300/tasks/abc300_b)
### 考察 
基本的な考察として、
・縦のシフトと横のシフトはどのような順番でも各回数が同じであれば結果も同じ
・縦のシフトと横のシフトはそれぞれH回、W回で元に戻るので0~H-1回、0~W-1回、試行すれば良い
後は愚直実装。
多次元リストのコピーにはcopy.deepcopyの使用が無難。

### コード
```python
from copy import deepcopy

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
B = [list(input()) for _ in range(H)]

for s in range(H):
    AA = deepcopy(A)
    for i in range(H):
        for j in range(W):
            A[i][j] = AA[(i + 1) % H][j]
    for t in range(W):
        AA = deepcopy(A)
        for j in range(W):
            for i in range(H):
                A[i][j] = AA[i][(j+1) % W]

        if A == B:
            print("Yes")
            exit()

print("No")
```
このコードは縦のシフトを１回づつ、横のシフトを１回づつとループを回していますが、縦のシフト$s$回、横のシフト$t$回をまとめて表現した方が簡潔になります。
```python
from copy import deepcopy

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
B = [list(input()) for _ in range(H)]

for s in range(H):
    for t in range(W):
        AA = deepcopy(A)
        for i in range(H):
            for j in range(W):
                AA[i][j] = A[(i + s) % H][(j + t) % W] 

        if AA == B:
            print("Yes")
            exit()

print("No")
```


## C - Cross
#### 問題ページ : [C - Cross](https://atcoder.jp/contests/abc300/tasks/abc300_c)
### 考察 
全マスマス(i,j)に対してこれを左上とするサイズ$0 ～ \frac{min(H,W)}{2}$のバツ印があるかを全判定しても計算量的には間に合います。
### コード
```python
H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
N = min(H,W)

ans = [0] * (N+1)
for i in range(H):
    for j in range(W):
        for kk in range(1,N // 2 + 1):
            k = kk * 2
            if i + k >= H or j + k >= W:
                break

            flag = True
            for s in range(k+1):
                if C[i+s][j+s] != "#" or C[i+ k- s][j+s] != "#":
                    flag = False
                                    
                if i-1 >= 0 and j - 1 >= 0 and C[i-1][j-1] == "#":flag = False
                if i-1 >= 0 and j + k < W and C[i-1][j+k] == "#":flag = False
                if i+k < H and j-1 >= 0 and C[i+k][j-1] == "#":falge = False
                if i+k < H and j+k < W and C[i+k][j+k] == "#":flage = False
                    
            if flag:
                ans[kk] += 1

print(*ans[1:])
```
問題文にある
・バツ印を構成するマス以外に # は書かれていません。
・異なるバツ印を構成するマス同士は頂点を共有しません
を正しく理解するとここまでしなくてもよく、もう少し簡潔になります。
```python
H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
N = min(H,W)

ans = [0] * (N+1)
for i in range(H):
    for j in range(W):
        if C[i][j] != "#":continue
        if i > 0 and j > 0 and C[i-1][j-1] == "#":continue
        k = 0
        while k + i < H and k + j < W and C[i+k][j+k] == "#":
            k += 1
        ans[k//2] += 1
print(*ans[1:])
```

## D - AABCC
#### 問題ページ : [D - AABCC](https://atcoder.jp/contests/abc300/tasks/abc300_d)
### 考察
結論からいうとあらかじめエラトステネスの篩で素数を列挙し、a,b,cの3重ループ全探索で解を求めることができます。
エラトステネスの篩で求める素数の上限ですが、$a^2bc^2 \leq\ N \leq10^{12}$なので高々$10^6$までの素数を列強すればOKです。
またループを回す際には
```math
\begin{align}
a^5\ >\ N  \\
a^2b^3\ >\ N \\
a^2bc^2\ >\ N \\
\end{align}
```
でbreakをかけ不要な計算を省きます。
### コード
```python
# エラトステネスの篩
def eratos(n):
    primes = [True] * (n+1)
    primes[0], primes[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if primes[i]:
            for j in range(i**2, n+1, i):
                primes[j] = False
    ret = [num for num, is_prime in enumerate(primes) if is_prime]
    return ret

N = int(input())
P = eratos(10**6)
num = len(P)

ans = 0
for i in range(num):
    a = P[i]
    if a ** 5 > N:break
    for j in range(i+1,N):
        b = P[j]
        if (a ** 2) * (b ** 3) > N:break
        for k in range(j+1,N):
            c = P[k]
            if a * a * b * c * c <= N:
                ans += 1
            else:
                break

print(ans)
```

## E - Dice Product 3
#### 問題ページ : [E - Dice Product 3](https://atcoder.jp/contests/abc300/tasks/abc300_e)
### 考察 
求める確率を$f(N)$と表すこととします。$N=15$の例を考えてみますと次の式が成り立ちます。
$$f(15)\ =\ f(3)\ \times\ (5を引く確率)\ +\ f(5)\ \times\ (3を引く確率) $$
ここで$2,4,6$を引いて15となることは無いことに注意してください。
また$(5を引く確率)$や$(3を引く確率)$は単純には$\frac{1}{6}$なのですが、その前に$1$を$０～ \infty$回だしても良いことを考慮すると初項$\frac{1}{6}$、項比$\frac{1}{6}$の無限級数の和で$\frac{1}{5}$となります（解説放送によると$1$がでたら振り直しと考え$2$~$5$のでる確率が等確率で$\frac{1}{5}$と考えて良いそうです）。
ここまでの考え方を元にメモ化つき再帰で実装します。
なお$mod\ 998244353$における$\frac{1}{5}$は$pow(5,\ -1,\ 998244353)$で処理します。
### コード
```python
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

md = 998244353 

N = int(input())

d = defaultdict(int)

def dfs(n):
    if n in d:return d[n]

    if n == 1:
        d[n] = 1
        return d[n]
    
    ret = 0
    for i in range(2,7):
        if n % i == 0:
            ret += pow(5, -1, md) * dfs(n // i)
            ret %= md
    d[n] = ret
    return d[n]

print(dfs(N))
```

## F - More Holidays
#### 問題ページ : [F - More Holidays](https://atcoder.jp/contests/abc300/tasks/abc300_f)
### 考察 
### コード
```python
```

## G - P-smooth number
#### 問題ページ : [G - P-smooth number](https://atcoder.jp/contests/abc300/tasks/abc300_g)
### 考察 
### コード
```python
```

## Ex - Fibonacci: Revisited
#### 問題ページ : [Ex - Fibonacci: Revisited](https://atcoder.jp/contests/abc300/tasks/abc300_h)
### 考察 
### コード
```python
```



青色diff以上は後日挑戦