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回の記事の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:])

補足

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

筆者について

その他

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

最後に一言

覚悟があるから幸福なのだ．