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