🙆♀️
【python】100日後に緑コーダーになるためのABC188 A,B,C,D,E問題【10日目】
はじめに
100日後に緑コーダーになるためにAtcoder Beginner Contest188の解説を行います。
今回はA ~ E問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。
対象読者
灰・茶コーダー
A - Three-Point Shot
解法
入力の大小を比較してif文
出題者の意図
if文が使えるか
コード
point = list(map(int,input().split()))
if min(point) + 3 > max(point):
print('Yes')
else:
print('No')
B - Orthogonality
解法
内積の計算
出題者の意図
リストから値を取り出して処理できるか
コード
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
judge = 0
for i in range(N):
judge += A[i]*B[i]
if judge == 0:
print('Yes')
else:
print('No')
C - ABC Tournament
解法
トーナメントを前半と後半に分けて決勝の人間を探す
出題者の意図
トーナメントの仕組を理解しているか
max関数、min関数を使えるか
考察
トーナメントは値が最も大きい人が優勝する
トーナメントを前半と後半に分けて、各ブロックでの優勝者同士が決勝戦に進む
コード
N = int(input())
A = list(map(int,input().split()))
winner1 = max(A[:2**(N-1)])
winner2 = max(A[2**(N-1):])
ans = A.index(min(winner1,winner2))+1
print(ans)
D - Snuke Prime
解法
高速いもす法
出題者の意図
いもす法を高速化できるか
考察
いもす法の問題なのは明白だが制約
そこで座標圧縮して、いもす法をする
コード
N, C = map(int,input().split())
event = [] #始点、終点、コストを格納
for i in range(N):
a,b,c = map(int,input().split())
event.append([a-1,c])
event.append([b,-c])
event.sort()
fee = 0
t = 0
ans = 0
for day,cost in event:
if day != t:
ans += min(C,fee)*(day-t)
t = day
fee += cost
print(ans)
E - Peddler
解法
DPを使って最小金額で買える商品を探索
出題者の意図
DAG(有向非巡回グラフ)に気付けるか
適切にDPできるか
考察
どのようなグラフになるか考える
- 有向であること
- 閉路を含まないこと
以上のことからDAGだと分かる
DAGはDPで解けることが知られているのでDPを使いましょうという問題でした（※しかし、厳密には間違った解釈らしいのでDAGを見つけたらDPの可能性を考えてみる程度に思っておいたほうがいいでしょう。書籍などで学んでみてください）
コード
N ,M = map(int,input().split())
A = list(map(int,input().split()))
G = [[] for _ in range(N)]
for i in range(M):
a, b = map(int, input().split())
G[a-1].append(b-1)
INF = float('inf')
dp = [INF] * N
for i in range(N):
for v in G[i]:
dp[v] = min(dp[v],dp[i],A[i])
ans = -INF
for i in range(N):
ans = max(ans,A[i]-dp[i])
print(ans)
Discussion