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

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

# A問題
- 色`C`に該当したもので条件分岐する．
- 色`C`以外を，最小値を取り出す関数`min`に渡すことで，必要な最小金額を得る．
```A.py
"""
<方針>
- 色`C`に該当したもので条件分岐する．
- 色`C`以外を，最小値を取り出す関数`min`に渡すことで，必要な最小金額を得る．
"""
# 標準入力を受け取る．
R, G, B = map(int, input().split())
# 標準入力を受け取る．
C = input()

# Blueを除外する時，
if(C == "Blue"):
  print(min(R, G))
# Redを除外する時，
if(C == "Red"):
  print(min(G, B))
# Greenを除外する時，
if(C == "Green"):
  print(min(B, R))
```

# B問題
- 点`A`を原点`O`に持ってくるように，点`B`と点`C`も並行移動する．
- 点`B`と点`C`の内積が`0`だったら，直角3角形なので，`Yes`を出力し，プログラムを関数`exit`で終了する．
- 同様に，点`B`，点`C`を原点`O`に持ってきて同じ議論をする．
- 同様の処理をまとめると楽．今回は`judge`という関数でまとめた．
```B.py
"""
<方針>
- 点`A`を原点`O`に持ってくるように，点`B`と点`C`も並行移動する．
- 点`B`と点`C`の内積が`0`だったら，直角3角形なので，`Yes`を出力し，プログラムを関数`exit`で終了する．
- 同様に，点`B`，点`C`を原点`O`に持ってきて同じ議論をする．
- 同様の処理をまとめると楽．今回は`judge`という関数でまとめた．
"""
# 標準入力を受け取る．
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

# 
def judge(M, P, Q):
  # 点Mが点Oに行くように，全ての点を並行移動する．
  X1 = P[0] - M[0]
  Y1 = P[1] - M[1]
  X2 = Q[0] - M[0]
  Y2 = Q[1] - M[1]
  
  # 内積が0の時，
  if(Y1*Y2 + X1*X2 == 0):
    # Yesを出力する．
    print("Yes")
    # プログラムを終了する．
    exit()

# 点Aを原点Oに移動するように並行移動する．
judge(A, B, C)
# 点Bを原点Oに移動するように並行移動する．
judge(B, C, A)
# 点Cを原点Oに移動するように並行移動する．
judge(C, A, B)

# プログラムを終了できなかった時，直角3角形ではないので，Noを出力する．
print("No")
  
```

# C問題
## 方針
- 最小和`mi`と最大和`ma`を記録する．
- `mi<=0<=ma`の関係であれば，和で`0`を実現できる．
- 和を`0`にする方法は，最小和に近づくように貪欲に`l`を選択し，後半で`r`側を選択して0に調整する．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 最小和`mi`と最大和`ma`を記録する．
- `mi<=0<=ma`の関係であれば，和で`0`を実現できる．
- 和を`0`にする方法は，最小和に近づくように貪欲に`l`を選択し，後半で`r`側を選択して0に調整する．
"""
# 標準入力
N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)]

# 最小和と最大和を作成する．
mi = 0
ma = 0
for i in range(N):
  l, r = LR[i]
  mi += l
  ma += r

# 最小和と最大和の間に0がある時，和を0にすることができる．
if(mi<=0<=ma):
  # できる！！
  print("Yes")
  # 目的値
  level = ma
  # 0を実現する個々の値を格納するリスト
  ans = []
  # 実現値を一つずつ手にいれる
  for i in range(N):
    l, r = LR[i]
    # rとlの差分d
    d = r-l
    # 実現値
    tmp = None
    # 貪欲にlを選択する．
    if(d<level):
      tmp = l
      # lに寄っただけ，目的値を下げる
      level -= d
    else:
      # r側を選択することで，調整する．
      tmp = r-level
      # 目的値を0にする
      level = 0
    # 実現値をリストに追加する．
    ans.append(tmp)
  # 実現値を出力する．
  print(*ans)
# 和を0にできないから，Noを出力して終了する．
else:
  # できない．．
  print("No")
```

# D問題

- ダイクストラで解く．
- 詳細はコメントを追ってください．(解説が雑くてごめん... 最近色々一杯一杯で．．．)．
```D.py
"""
<方針>
- ダイクストラで解く．
- 詳細はコメントを追ってください．(解説が雑くてごめん... 最近色々一杯一杯で．．．)．
"""
import heapq

# 標準入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
# グラフ構築
E = [[] for _ in range(N)]
for i in range(M):
  u, v, B = map(int, input().split())
  u -= 1
  v -= 1
  # u→vで，コストはvの頂点とコストBの和とする．
  E[u].append([v, A[v]+B])
  # v→uで，コストはuの頂点とコストBの和とする．
  E[v].append([u, A[u]+B])

# ダイクストラ
ans = [float('inf')] * N
ans[0] = 0 # 最初の点はコストを0とする．(最後に全ての頂点に対して，A[0]のコストを足して出力する．)
# 最初の点を入れる
q = [[0, 0]]

while len(q) > 0:
  # 取り出す．
  min_cost, min_point = heapq.heappop(q)
  
  # 更新が目に見えてない時は，無視
  if(min_cost>ans[min_point]):
    continue
  
  # 次の点を取り出す．
  for goal, cost in E[min_point]:
    # 更新条件
    if ans[min_point] + cost < ans[goal]:
      # 更新
      ans[goal] = ans[min_point] + cost
      # 次へ
      heapq.heappush(q, [ans[min_point] + cost, goal])

# 出力
print(*list(map(lambda x:x+A[0], ans[1:])))
```

# E問題
- 公式解説と一緒です．

```E.py
"""
<方針>
- 公式解説と一緒です．
"""
N = int(input())
A = list(map(int, input().split()))

mod = 998244353

# i, j番目のAの値を第1と第2の項にもち，項数がlを成す組み合わせの数．
dp =[[[0]*(N+1) for _ in range(N)] for _ in range(N)]

# iを降順から見る
for i in reversed(range(N)):
  # i<jの範囲で見る
  for j in range(i+1, N):
    # iとjだけでは，組み合わせとして1通り
    dp[i][j][2] = 1
    # 項数が2より大きい時への遷移を考える．
    for l in range(2, N-i):
      # j<kの範囲で見る
      for k in range(j+1, N):
        # 公差が等しい時，
        if(A[k]-A[j]) == (A[j]-A[i]):
          # 遷移する．
          dp[i][j][l+1] += dp[j][k][l];dp[i][j][l+1] %= mod

# 項数がiの時の組み合わせの通り
ans = [0]*(N+1)
# 項数が1個の時は当然N個
ans[1] = N
# iを全てみる
for i in range(N):
  # jを全てみる
  for j in range(N):
    # 項数を見る
    for l in range(N-i+1):
      # 項数を足し合わせる
      ans[l] += dp[i][j][l];ans[l] %= mod

# 出力
print(*ans[1:])
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc362)
- [E問題の公式解説](https://atcoder.jp/contests/abc362/editorial/10399)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(oooox--)](https://atcoder.jp/users/mattsunkun/history/share/abc362)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc362/submissions/55741344)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc362/submissions/55741683)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc362/submissions/55742590)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc362/submissions/55742124)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc362/submissions/55741265)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 覚悟があるから幸福なのだ．