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

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

# A問題
- 我々がすることは特にない．
- 計算機に頑張ってもらう．
```A.py
"""
<方針>
- 我々がすることは特にない．
- 計算機に頑張ってもらう．
"""
# 入力
A, B = map(int, input().split())
# 計算
ans = (A+B)**2
# 出力
print(ans)
```

# B問題
- 九九の値 `num` を順番に見ていく．
- それが `X` と合致しなければ，答えに足す．
```B.py
"""
<方針>
- 九九の値 `num` を順番に見ていく．
- それが `X` と合致しなければ，答えに足す．
"""
# 入力
X = int(input())

# 総和
ans = 0

# 九九をみる
for i in range(1, 10):
  for j in range(1, 10):
    # 九九の値を取得
    num = i*j
    # Xに一致しなければ
    if(num!=X):
      # 総和に足す
      ans += num

# 出力
print(ans)
```

# C問題
## 方針
- 明らかに `O(N)` は間に合わない．
- 桁ごとでうまくみていけば，あとは実装力の問題だ．
  - `L~R` という条件が知りたければ，`X` 以下さえ分かる関数 `snake` を求めれば， `snake(R) - snake(L-1)` を求めれば良い．
  - <パターンA> `X` の桁数よりも小さい桁を全部列挙すれば良い．
  - <パターンB> `X` の桁数において，`X` の先頭の数を `X` の実際の先頭の数いかを試せば良い．
  - <パターンC> `X` の桁数において，`X` の先頭も固定した状態で考える．その時，「`X` の先頭の数」進数で考えると良さそう．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 明らかに `O(N)` は間に合わない．
- 桁ごとでうまくみていけば，あとは実装力の問題だ．
  - `L~R` という条件が知りたければ，`X` 以下さえ分かる関数 `snake` を求めれば， `snake(R) - snake(L-1)` を求めれば良い．
  - <パターンA> `X` の桁数よりも小さい桁を全部列挙すれば良い．
  - <パターンB> `X` の桁数において，`X` の先頭の数を `X` の実際の先頭の数いかを試せば良い．
  - <パターンC> `X` の桁数において，`X` の先頭も固定した状態で考える．その時，「`X` の先頭の数」進数で考えると良さそう．
"""
# 入力
L, R = map(int, input().split())

def snake(X):
  # L==10の時，L-1==0になるため，その対処
  if X<=9:return 0
  
  # 基本情報
  block = str(X)
  head = int(block[0])
  length = len(block)
  
  # 出力
  ans = 0
  
  ## パターンA
  for i in range(2, length):
    for j in range(1, 10):
      ans += j**(i-1)
  
  ## パターンB
  for i in [length]:
    for j in range(1, head):
      ans += j**(i-1)

  ## パターンC
  tmp = "" # head進数を作る
  fla = True # head<=iを見てないフラグ
  for ind, s in enumerate(block[1:]):
    i = int(s)
    if(head>i and fla):
      tmp += s
    else:
      tmp += str(head-1)
      fla = False
  # head進数の計算
  for i, s in enumerate(reversed(tmp)):
    ans += int(s)*(head**i)
  
  # 「10」のパターンを足す
  ans += 1
  
  # 出力
  return ans

ans = snake(R)-snake(L-1)

print(ans)
```

# D問題
- マスの縦横インデックスの和を2で割った余り(`(y+x)%2`)によって縦or横に移動できるかを制限をかけておく．
  - これを2通り試せば良い．
- `Python` の再帰は遅いので，非再帰BFSで実装する．
  - `popleft` をすると，`BFS` になり，`pop` をすると，`DFS` になる．
```D.py
"""
<方針>
- マスの縦横インデックスの和を2で割った余り(`(y+x)%2`)によって縦or横に移動できるかを制限をかけておく．
  - これを2通り試せば良い．
- `Python` の再帰は遅いので，非再帰BFSで実装する．
  - `popleft` をすると，`BFS` になり，`pop` をすると，`DFS` になる．
"""
from collections import deque
# 入力
H, W = map(int, input().split())
INF = float("inf")
SS = []
start = None
goal = None
for i in range(H):
  _S = input()
  S = []
  for j, s in enumerate(_S):
    match s:
      case ".":
        S.append(INF)
      case "#":
        S.append(-1)
      case "S":
        S.append(INF)
        start = (i, j)
      case "G":
        S.append(INF)
        goal = (i, j)
  SS.append(S)

# BFS
def bfs(way):
  # 盤面を新しく作成
  TT = []
  for S in SS:
    TT.append(S[:])
  
  # deque
  q = deque()
  
  # 初期値
  TT[start[0]][start[1]] = 0
  q.append(start)
  
  # ループ
  while q:
    # 取り出す
    y, x = q.popleft() # BFS
    
    # 上下左右への移動
    for dy, dx in [
      (-1, 0), 
      (0, -1), 
      (1, 0), 
      (0, 1), 
      ]:
        # 新しいindex
        Y = y + dy
        X = x + dx
        
        # 枠内にあるか
        if(0<=Y<H and 0<=X<W):
          # 上下移動or左右移動を許可
          if(((y+x)%2==way)==(dy==0)):
            # 新しいコスト
            cost = TT[y][x] + 1
            # 新しいコストの方が条件が良ければ，更新してdequeに入れる
            if(cost < TT[Y][X]):
              TT[Y][X] = cost
              q.append([Y, X])
  
  # GOALの値を出力
  return TT[goal[0]][goal[1]]

# 上下or左右パターンの両者のうち，最適な方を選択
ans = min(bfs(0), bfs(1))

# 到達できなければ，-1にする．
if(ans == INF):
  ans = -1

# 出力
print(ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc387)
- [C問題の<パターンC>の発想](https://atcoder.jp/contests/abc387/submissions/61393179)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc387/submissions/61474857)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc387/submissions/61474899)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc387/submissions/61474069)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc387/submissions/61474791)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- C問題の<パターンC>の発想は友人の力を借りました．