ABC429をPythonで

Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）の解答等の速報的まとめ

A問題

問題文のまま

A

n, m = map(int, input().split())
for i in range(n):
    if i < m:
        print("OK")
    else:
        print("Too Many Requests")

B問題

合計と$M$との差が配列内にあるか調べる

B

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

sum_a = sum(a)
if sum_a - m in a:
    print("Yes")
else:
    print("No")

C問題

「同じ数字から2個取る＋それ以外の数字から１つ取る」組み合わせを各数字ごとに計算する

C

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

d = dict()
for a_i in a:
    if a_i not in d:
        d[a_i] = 0
    d[a_i] += 1

ans = 0
for key, val in d.items():
    ans += val * (val - 1) * (n - val) // 2

print(ans)

D問題

一周だけの場合は累積和と尺取り法で何人になるか求められる
２週以上するときは最初に$c$を$n$で割って余りを上の計算で用いればいい

D

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

d = dict()
for a_i in a:
    if a_i not in d:
        d[a_i] = 0
    d[a_i] += 1

sort_a = sorted(d.items(), key=lambda x:x[0])
lst = list()
keys = list()
last = sort_a[-1][0]
for key, val in sort_a:
    diff = (key - last) % m
    lst.append(val)
    keys.append((key, diff))
    last = key

accu = [0]
for l_i in lst + lst:
    accu.append(accu[-1] + l_i)

l = c // n
k = c % n

if len(keys) == 1:
    count = l * n + (n if k > 0 else 0)
    print(count * m)
else:
    ans = 0
    right = 0
    for i, (key, diff) in enumerate(keys):
        while accu[right] - accu[i] < k:
            right += 1
        ans += (l * n + accu[right] - accu[i]) * diff

    print(ans)