ABC423をPythonで（A～D）

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

A問題

1000ごとに引き出せるか調べる

A

x, c = map(int, input().split())

ans = 0
for i in range(1000, x + 1, 1000):
    tax = i * c // 1000
    if i + tax <= x:
        ans = i

print(ans)

B問題

実際に両端から移動させ、間の部屋数を返す
鍵がかかっていないときはすれ違うので注意

B

n = int(input())
l = list(map(int, input().split()))

left, right = 0, n

for l_i in l:
    if l_i == 0:
        left += 1
    else:
        break

for l_i in l[::-1]:
    if l_i == 0:
        right -= 1
    else:
        break

print(max(right - left - 1, 0))

C問題

端のカギがかかっているのは無視できる

よって端から順にみて0が出るまでは無視
出てからは 0のときans+=1, 1のときans+=2
をrまで両端から調べる

C

n, r = map(int, input().split())
l = list(map(int, input().split()))

ans = 0
flag = False
for i in range(r):
    if l[i] == 0:
        flag = True
    if flag:
        ans += l[i] + 1

flag = False
for i in range(n - 1, r - 1, -1):
    if l[i] == 0:
        flag = True
    if flag:
        ans += l[i] + 1

print(ans)

D問題

heapで出る時間と顧客数を管理

D

from heapq import heappush, heappop

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

lst = []
ind = 0
time = 0
total = 0
ans = []

while len(ans) < n:
    a, b, c = data[ind]
    time = max(time, a)
    while lst and lst[0][0] <= time:
        t, c_i = heappop(lst)
        total -= c_i

    while total + c > k:
        t, c_i = heappop(lst)
        time = t
        total -= c_i

    ans.append(time)
    total += c
    heappush(lst, (time + b, c))
    ind += 1

for ans_i in ans:
    print(ans_i)