ABC361(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# ABC361(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# A問題
- 標準入力を受け取る．
- `A` をリストで受け取り，`0-indexed` に注意し， `insert` メソッドで `K` 番目に `X` を挿入する．
- アンパックをいう方法で空白区切りで出力する．
```A.py
"""
<方針>
- 標準入力を受け取る．
- `A` をリストで受け取り，`0-indexed` に注意し， `insert` メソッドで `K` 番目に `X` を挿入する．
- アンパックをいう方法で空白区切りで出力する．
"""
N, K, X = map(int, input().split())
A = list(map(int, input().split()))

A.insert(K, X)
print(*A)
```

# B問題
- `x, y, z` のそれぞれにおいて，区間が交差しないといけないので，区間の最大と最小を比較すれば良い．

```B.py
"""
<方針>
- `x, y, z` のそれぞれにおいて，区間が交差しないといけないので，区間の最大と最小を比較すれば良い．
"""
# 入力を受け取る．
abcdef = list(map(int, input().split()))
ghijkl = list(map(int, input().split()))

# 体積が正にならないときにTrueになるフラグ
ng = False

# x, y, z の3種類確認する．
for i in range(3):
  # 区間が交差しないとき，
  if ghijkl[i+3]<=abcdef[i] or abcdef[i+3]<=ghijkl[i]:
    # 体積が正にならない．
    ng = True
    
# 出力
if ng:
  print("No")
else:
  print("Yes")
```

# C問題
## 方針
- `K` 個削除し，残った要素の順序を保つ `B` と書いてあるが， 「順序を保つこと」は今回の問題においては重要ではない．
- 最大と最小を考えるので， `A` はソートする．以下， `A` は昇順であるとする．
- `A` の外側を `K` 個削った状態で，最大と最小の差を考えれば良い．
- `A` の左端を `i` 個削って， `A` の右端を `K-i` 個削って，最も差が小さくなったものを出力すれば良い．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `K` 個削除し，残った要素の順序を保つ `B` と書いてあるが， 「順序を保つこと」は今回の問題においては重要ではない．
- 最大と最小を考えるので， `A` はソートする．以下， `A` は昇順であるとする．
- `A` の外側を `K` 個削った状態で，最大と最小の差を考えれば良い．
- `A` の左端を `i` 個削って， `A` の右端を `K-i` 個削って，最も差が小さくなったものを出力すれば良い．
"""

# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))

# Aをソートする．
A.sort()

# (最大と最小の差)の最小値を求める．
# 初期値は無限とする．
ans = float("inf")
for i in range(K+1):
  # 小さい方を更新
  ans = min(ans, A[i+N-K-1]-A[i])
# 出力
print(ans)
```

# D問題
- 公式解説と一緒です．
- 筆者は，再帰を高速化してもダメだったので，非再帰で実装しました．
```D.py
"""
- 公式解説と一緒です．
- 筆者は，再帰を高速化してもダメだったので，非再帰で実装しました．
"""

# このおまじないではTLEした．
"""
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys
sys.setrecursionlimit(10**6)
"""

from collections import deque

N = int(input())
S = list(input())
T = list(input())

# 個数が一致してない時は到達不可能．
if(S.count("W")!=S.count("W")):
  print(-1)
  exit()

# 末尾に "." を２つつける．
S.append(".")
S.append(".")
T.append(".")
T.append(".")

# 連想配列にアクセスするときに利用する．
def ind(S):
  return "".join(S)

# 連想配列．
## key: 状態
## val: 到達するのに必要なステップ数
dp = {}

# 初期状態は0ステップで移動可能
dp[ind(S)] = 0

q = deque()
q.append(S)

while q:
  S = q.popleft()
  # "."が連続している場所を取得．
  a = None
  for i in range(N+1):
    if(S[i]=="."):
      a = i
      break
  
  # 遷移
  for i in range(N+1):
    # 連続している2箇所を取得する．
    x = S[i]
    y = S[i+1]
    # 両方とも"."でなければ，
    if(x != "." and y != "."):
      # 次の状態を作る．
      tmp = S[:]
      # 石を取り除く
      tmp[i] = "."
      tmp[i+1] = "."
      # 石を移動する．
      tmp[a] = x
      tmp[a+1] = y
      
      # 状態遷移．
      if((not ind(tmp) in dp) or (dp[ind(S)]+1<dp[ind(tmp)])):
      # if not ind(tmp) in dp:
        dp[ind(tmp)] = dp[ind(S)] + 1
        q.append(tmp)

# 出力
if(ind(T) in dp):
  print(dp[ind(T)])
else:
  print(-1)

```
# E問題
- 公式解説と一緒です．
```E.py
"""
<方針>
- 公式解説と一緒です．
"""
from collections import deque

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N-1)]

# グラフの辺を構築
E = [[] for _ in range(N)]
for a, b, c in ABC:
  a -= 1
  b -= 1
  E[a].append([b, c])
  E[b].append([a, c])

# 引数を起点として，最も遠い点とそのコストを出力する．
def far(start):
  vis = [None]*N
  vis[start] = 0
  q = deque()
  q.append(start)
  while q:
    a = q.popleft()
    
    for b, c in E[a]:
      if vis[b] is None:
        vis[b] = vis[a] + c
        q.append(b)
  
  v = -1
  D = -1
  for i, d in enumerate(vis):
    if(D<d):
      D = d
      v = i
  
  return v, D

# 最初の頂点から最も遠い頂点を取得
v, _ = far(0)
# 最も遠い頂点から見た，最も遠い距離を取得
_, D = far(v)

# 答えの計算
ans = 2*sum(map(lambda x: x[2], ABC)) - D
print(ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc361)
- [E問題の公式解説](https://atcoder.jp/contests/abc361/editorial/10354)
- [E問題の公式解説](https://atcoder.jp/contests/abc361/editorial/10329)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(oooxx--)](https://atcoder.jp/users/mattsunkun/history/share/abc361)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc361/submissions/55341609)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc361/submissions/55341718)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc361/submissions/55341891)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc361/submissions/55340972)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc361/submissions/55341513)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- *十で神童、十五で才子、二十歳過ぎれば只の人*