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問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 覚悟があるから幸福なのだ．