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

# [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回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`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))))
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc375)
- [F問題の公式解説](https://atcoder.jp/contests/abc375/editorial/11134)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc375/submissions/58800454)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc375/submissions/58800633)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc375/submissions/58803029)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc375/submissions/58824906)
- [解説で示したF問題の提出](https://atcoder.jp/contests/abc375/submissions/58826427)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- この記事も1年書いたらやめようかな．