🙆‍♀️

【python】100日後に緑コーダーになるためのABC188 A,B,C,D,E問題【10日目】

2021/11/28に公開約2,300字

はじめに

100日後に緑コーダーになるためにAtcoder Beginner Contest188の解説を行います。
今回はA ~ E問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。

対象読者

灰・茶コーダー

A - Three-Point Shot

https://atcoder.jp/contests/abc188/tasks/abc188_a

解法

入力の大小を比較してif文

出題者の意図

if文が使えるか

コード

point = list(map(int,input().split()))

if min(point) + 3 > max(point):
    print('Yes')
else:
    print('No')

B - Orthogonality

https://atcoder.jp/contests/abc188/tasks/abc188_b

解法

内積の計算

出題者の意図

リストから値を取り出して処理できるか

コード

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

https://atcoder.jp/contests/abc188/tasks/abc188_c

解法

トーナメントを前半と後半に分けて決勝の人間を探す

出題者の意図

トーナメントの仕組を理解しているか
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

https://atcoder.jp/contests/abc188/tasks/abc188_d

解法

高速いもす法

出題者の意図

いもす法を高速化できるか

考察

いもす法の問題なのは明白だが制約1≤ai≤bi≤10^9から愚直にいもす法を使うと間に合わない
そこで座標圧縮して、いもす法をする

コード

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

https://atcoder.jp/contests/abc188/tasks/abc188_e

解法

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

ログインするとコメントできます