[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回の記事の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)

補足

関係するリンク(参考文献など)

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

C問題の<パターンC>の発想は友人の力を借りました．