ABC330をPythonで（A~E）

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

A問題

問題通りに調べる

A

_,L=map(int,input().split())
print(sum(a_i>=L for a_i in map(int, input().split())))

B問題

その数$a_i$が
$L<=a_i<=R$のときは$a_i$
$a_i<L$のときは$L$
$R<a_i$のときは$R$

B

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

ans = []
for a_i in a:
    if l<= a_i <= r: ans.append(a_i)
    elif a_i < l:ans.append(l)
    else:ans.append(r)

print(*ans)

C

尺取り法で調べる

C

d = int(input())

ans = float("inf")
x = 10 ** 6
for y in range(10 ** 6 + 1):
    while x >= 0 and x ** 2 + y ** 2 > d:
        x -= 1
    a, b = abs(x ** 2 + y ** 2 - d), abs((x + 1) ** 2 + y ** 2 - d)
    ans = min(ans, a, b)
    x += 1

print(ans)

D

oのある各地点において
その地点と同じ行と列にあるoの数-1の積の総和が答え

D

n = int(input())
x = [0] * n
y = [0] * n
data = []
for i in range(n):
    d = input()
    data.append(d)
    for j, d_i in enumerate(d):
        if d_i == "o":
            x[i] += 1
            y[j] += 1

ans = 0
for i, d in enumerate(data):
    for j, d_i in enumerate(d):
        if d_i == "o":
            ans += (x[i] - 1) * (y[j] - 1)

print(ans)

E

mexをheapで管理する
このときmexの候補は高々$n+1$なので
その範囲内で調べればよい

E

from heapq import heappop, heappush

n, q = map(int, input().split())
a = list(map(int, input().split()))

mex = [i for i in range(n + 10)]
d = {i:0 for i in range(n + 10)}
for a_i in a:
    if a_i in d:
        d[a_i] += 1

for _ in range(q):
    i, x = map(int, input().split())
    i -= 1
    if a[i] in d:
        d[a[i]] -= 1
        if d[a[i]] == 0:
            heappush(mex, a[i])
    a[i] = x
    if x in d:
        d[x] += 1


    while d[mex[0]] > 0:
        heappop(mex)
    print(mex[0])