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

Posted at 2024-10-15

[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年書いたらやめようかな．

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up