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

A問題

席が両隣座っていて，真ん中は空いているケースを隈なく探す．
index(0-indexed) は 1~N-1 にみれば良い．

A.py

"""
<方針>
- 席が両隣座っていて，真ん中は空いているケースを隈なく探す．
- `index(0-indexed)` は `1~N-1` にみれば良い．
"""
# 入力
N = int(input())
S = input()

ans = 0
# 1~N-1をシミュレーションする．
for i in range(1, N-1):
  # 両隣が座っていて，真ん中が空いているケース
  if(S[i-1] == S[i+1] == "#" and S[i] == "."):
    ans += 1
# 出力
print(ans)

B問題

高橋くんを実際に歩かせてみよう！！

B.py

"""
<方針>
- 高橋くんを実際に歩かせてみよう！！
"""
# 入力
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
# 最後は原点に移動するため
XY.append([0, 0])
# 高橋くんの現在の位置．最初は原点
now = (0, 0)
# 高橋くんが歩いたコスト
ans = 0
# 高橋くんを歩かせる
for i in range(N+1):
  # 高橋くんの現在地
  x, y = now
  # 入力(次の目的地)
  X, Y = XY[i]
  # コストを更新
  ans += ((x-X)**2+(y-Y)**2)**(0.5)
  # 高橋くんの位置を更新
  now = (X, Y)
# 出力
print(ans)

C問題

方針

愚直に塗り替え操作を行うと，O(N^2) かかり，それを愚直にシミュレーションすると，合計 O(N^3) かかるため間に合わない．
頑張って，4 回操作を行うと元に戻るという性質に気づく．
実装
- 全体を 0~3 回操作したもの AA を用意する．
- 外側から内側に入っていくにつれて， 4 周期で AA のものを ans に反映させたものが答え．
注意点
- 入力の . と # をそのまま利用すると，定数倍の処理が重くなり， TLE する(testcase02~04)．
- 内部処理ではそれぞれを bool ，即ち，それぞれ，False と True に変更すると，AC する．

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- 愚直に塗り替え操作を行うと，`O(N^2)` かかり，それを愚直にシミュレーションすると，合計 `O(N^3)` かかるため間に合わない．
- 頑張って，`4` 回操作を行うと元に戻るという性質に気づく．
- 実装
  - 全体を `0~3` 回操作したもの `AA` を用意する．
  - 外側から内側に入っていくにつれて， `4` 周期で `AA` のものを `ans` に反映させたものが答え．
- 注意点
  - 入力の `.` と `#` をそのまま利用すると，定数倍の処理が重くなり， `TLE` する(`testcase02~04`)．
  - 内部処理ではそれぞれを `bool` ，即ち，それぞれ，`False` と `True` に変更すると，`AC` する．
"""
# 入力
N = int(input())
# TLE回避のため，TrueとFalseに変えて受け取る．
A = []
for i in range(N):
  a = list(input())
  _A = []
  for j in range(N):
    _A.append(a[j] == "#")
  A.append(_A)
      

## ４回周期のものを作る．
# 初期化処理
AA = [[[False]*N for _ in range(N)] for _ in range(4)]
# 0回操作のもの
AA[0] = A
# 1~3回操作
for h in range(3):
  for i in range(N):
    for j in range(N):
      AA[h+1][j][N-1-i] = AA[h][i][j]

# 答えを初期化
ans = [[False]*N for _ in range(N)]
# 適当な周期のものを反映させる
for i in range(N):
  for j in range(N):
    # 中心から最も離れている地点
    a = int(max(abs(i-(N//2-0.5)), abs(j-(N//2-0.5))))
    # 外側から見て，どれだけ中に入っているか
    b = N//2 - a
    # 適当な周期
    c = b%4
    # 反映(boolから元のものに戻すのを忘れずに)
    if(AA[c][i][j]):
      ans[i][j] = "#"
    else:
      ans[i][j] = "."

# 出力
for a in ans:
  print("".join(a))

D問題

アルファベットを数字に変換(T)して考える．
どのアルファベットを左右に持ってくるかで 26 ループをする．
左右に持ってくるアルファベット数値を仮に a とする．
- T で a が連続している部分と， a でない部分が連続している部分で分ける．
- a でない部分が中心に選ばれたと考え，その左右に存在する a の数で掛け算をする．
- a が 3 つ以上ある時は，中心も全て a のパターンがあるので，それを足す．

D.py

"""
<方針>
- アルファベットを数字に変換(`T`)して考える．
- どのアルファベットを左右に持ってくるかで `26` ループをする．
- 左右に持ってくるアルファベット数値を仮に `a` とする．
  - `T` で `a` が連続している部分と， `a` でない部分が連続している部分で分ける．
  - `a` でない部分が中心に選ばれたと考え，その左右に存在する `a` の数で掛け算をする．
  - `a` が `3` つ以上ある時は，中心も全て `a` のパターンがあるので，それを足す．
"""
# 入力
S = input()
# 数値に変換
T = [ord(S[i]) - ord("A") for i in range(len(S))]

# 答えの数
ans = 0
# 全てのアルファベットに注目する．
for a in range(26):
  # aの数を計算
  allCnt = T.count(a)
  # aが連続している回数のリスト
  A = []
  # aでない部分が連続している回数のリスト
  B = []
  # 現在aであるかどうか
  nowA = False
  # 現在の連続カウント
  nowCnt = 0
  # 数値を走査する
  for i in range(len(T)):
    # aのとき
    if(T[i] == a):
      # 連続
      if(nowA):
        nowCnt += 1
      # 変化
      else:
        nowA = True
        B.append(nowCnt)
        nowCnt = 1
    # aでない時
    else:
      # 変化
      if(nowA):
        nowA = False
        A.append(nowCnt)
        nowCnt = 1
      # 連続
      else:
        nowCnt += 1
  # aが一つもないパターンの例外処理のための番兵
  A.append(0)
  # 左側にあるaの数
  left = A[0]
  # 中心にaでない数値のパターンを答えに追加する．
  for i in range(1, len(B)):
    # 左と中心と右の掛け算
    ans += left*B[i]*(allCnt-left)
    # 左の数を増やす
    left += A[i]
  
  # aが3以上ある時
  if(allCnt>=3):
    # 組み合わせ(nCr)を足す．
    ans += (allCnt*(allCnt-1)*(allCnt-2))//(3*2*1)
# 出力
print(ans)

F問題

公式解説と一緒です．

F.py

"""
<方針>
- 公式解説と一緒です．
"""
# 入力
N, M, Q = map(int, input().split())
# 無限の定義
INF = float("inf")
# エッジ初期値
E = [[INF]*N for _ in range(N)]
# 自分への移動はノーコスト
for i in range(N):
  E[i][i] = 0

# 入力
ABC = []
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1
  b -= 1
  # 無向辺なので，双方向のコストを記録
  E[a][b] = c
  E[b][a] = c
  ABC.append([a, b, c])

# 入力
query = []
# グラフからエッジを除いていく
for i in range(Q):
  q = list(map(int, input().split()))
  match q:
    # エッジを除く時
    case [1, i]:
      i -= 1
      a, b, c = ABC[i]
      E[a][b] = INF
      E[b][a] = INF
      query.append([1, a, b, c])
    # 最短距離要求のとき
    case [2, x, y]:
      x -= 1
      y -= 1
      query.append([2, x, y])

# ワーシャルフロイド
for h in range(N):
  for i in range(N):
    for j in range(N):
      E[i][j] = min(E[i][j], E[i][h]+E[h][j])

# 答えの出力(最後に順番をreverseする)
ans = []
# 後ろからクエリを見る
for q in reversed(query):
  match q:
    # エッジを追加する時
    case [1, a, b, c]:
      # フルメッシュ更新
      for i in range(N):
        for j in range(N):
          E[i][j] = min(
            E[i][j], 
            E[i][a]+c+E[b][j], 
            E[i][b]+c+E[a][j]
            )
    # 最短距離を求める
    case [2, x, y]:
      ans.append(str(E[x][y] if E[x][y]!=INF else -1))

# 後ろ向きに出力して正順にする．
print("\n".join(list(reversed(ans))))

補足

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

筆者について

その他

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

最後に一言

この記事も1年書いたらやめようかな．