ABC430をPythonで

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

A問題

$a$以上$b$未満の時Yes

A

a, b, c, d = map(int, input().split())
if a <= c and b > d:
    print("Yes")
else:
    print("No")

B問題

対象のグリッドを一連の文字列にしてsetで個数確認

B

def get_string(x, y):
    res = ""
    for i in range(m):
        for j in range(m):
            res += s[x + i][y + j]
    return res


n, m = map(int, input().split())
s = [input() for _ in range(n)]

lst = list()
for i in range(n - m + 1):
    for j in range(n - m + 1):
        lst.append(get_string(i, j))

print(len(set(lst)))

C問題

左を固定して

• $a$が$A$個になる一番左端
• $b$が$B$個未満を維持する一番右端

を同時に尺取り法で調べて$a$と$b$の値から条件を満たす幅を計算する

C

n, a, b = map(int, input().split())
s = input()

ans = 0
count_a = count_b = 0
right_a, right_b = 0, -1
for left in range(n):
    while right_a < n and count_a + (s[right_a] == "a") < a:
        count_a += s[right_a] == "a"
        right_a += 1

    while right_b + 1 < n and count_b < b:
        if s[right_b + 1] == "b":
            if count_b + 1 == b:
                break
            else:
                count_b += 1
        right_b += 1
    # print(left, right_a, count_a, right_b, count_b)

    ans += max(right_b - right_a + 1, 0)

    if s[left] == "a":
        count_a -= 1
    else:
        count_b -= 1

print(ans)

D問題

SortedListを使って次に入れる数の前後の値を調べる
それとは別に辞書に一番近い点までの距離を記録して、答えに関与する差分だけ変化させる

D

from sortedcontainers import SortedList


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

INF = float("inf")
s = SortedList([0])
d = {0:INF}
ans = 0
for x_i in x:
    ind = s.bisect_left(x_i)
    left = s[ind - 1]
    right = INF if ind >= len(s) else s[ind]

    diff = min(x_i - left, right - x_i)
    d[x_i] = diff
    ans += diff

    if d[left] > x_i - left:
        if d[left] == INF:
            ans += x_i - left
            d[left] = x_i - left
            d[x_i] = diff
        else:
            ans -= d[left]
            ans += x_i - left
            d[left] = x_i - left

    if right < INF and d[right] > right - x_i:
        ans -= d[right]
        ans += right - x_i
        d[right] = right - x_i

    s.add(x_i)

    print(ans)

E問題

最長接尾辞か最長接頭辞のアルゴリズムを利用するんだろうな
とは思ったが、そこからさっぱりわからなかった