ABC463のPython解答（A～E）

AtCoder Beginner Contest 463の解答等の速報的まとめ

A問題

比の計算を掛け算で確認

A

x, y = map(int, input().split())
print("Yes" if x * 9 == y * 16 else "No")

B問題

列を順に確認

B

n, x = input().split()
target = ord(x) - ord("A")

ans = "No"
for _ in range(int(n)):
    s = input()
    if s[target] == "o":
        ans = "Yes"

print(ans)

C問題

SortedListを使って最大値を確認

C

from sortedcontainers import SortedList


n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]
q = int(input())
t = list(map(int, input().split()))

lst = list()
h = list()
for h_i, l_i in data:
    lst.append((l_i, h_i))
    h.append(h_i)

lst.sort()
h = SortedList(h)

d = dict()
l_ind = 0
for t_i in sorted(t):
    if t_i in d:continue
    while lst[l_ind][0] <= t_i:
        _, h_i = lst[l_ind]
        h.discard(h_i)
        l_ind += 1

    d[t_i] = h[-1]

for t_i in t:
    print(d[t_i])

D問題

二分探索
対象のスコアがとれるように布を選んだ時に$k$枚使っているかで判定

D

n, k = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]

data.sort(key=lambda x:[x[1], x[0]])

def check(target):
    last = -float("inf")
    count = 0
    for l_i, r_i in data:
        if last + target <= l_i:
            count += 1
            last = r_i

    return count >= k


ok, ng = 0, 10 ** 10
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

print(ok if ok > 0 else -1)

E問題

ダイクストラで計算
ワープは

• 都市$i$からワープ入口：コスト$X_i$
• ワープ入口からワープ出口：コスト$Y$
• ワープ出口から都市$j$：コスト$X_j$

と設定すれば一緒に計算できる

E

from heapq import heappop, heappush

n, m, y = map(int, input().split())

edge = [list() for _ in range(n + 2)]
for _ in range(m):
    u, v, w = map(int, input().split())
    edge[u - 1].append([v - 1, w])
    edge[v - 1].append([u - 1, w])

warp_in = n
warp_out = n + 1

edge[warp_in].append([warp_out, y])
x = list(map(int, input().split()))
for i, x_i in enumerate(x):
    edge[i].append([warp_in, x_i])
    edge[warp_out].append([i, x_i])

dist = [0] + [float("inf")] * (n + 10)
q = [[0, 0]]

while q:
    d_i, now = heappop(q)
    if dist[now] < d_i:
        continue
    for to, w in edge[now]:
        if dist[to] > d_i + w:
            dist[to] = d_i + w
            heappush(q, [d_i + w, to])

print(*dist[1:n])