ABC370をPythonで（A～D）

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）の解答等のまとめ

A問題

lとrが同じときはInvalid。それ以外はYesNoを条件に合わせて返す。

A

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

print("Invalid" if l == r else "YNeos"[r::2])

B問題

問題文通りに実行する

B

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

now = 1
for i in range(1, n + 1):
    # print(now, i, ":", min(now, i), max(now, i))
    now = a[max(now, i) - 1][min(now, i) - 1]

print(now)

C問題

辞書順で早くなるものを先頭から順に変更して
そのあとに後ろから遅くなるものを変更していく

C

s = list(input())
t = list(input())

lst = []
for s_i, t_i in zip(s, t):
    if s_i < t_i:
        lst.append(-1)
    elif s_i == t_i:
        lst.append(0)
    else:
        lst.append(1)

x = []
for i in range(len(lst)):
    if lst[i] == 1:
        s[i] = t[i]
        x.append("".join(s))

for i in range(len(lst) - 1, -1, -1):
    if lst[i] == -1:
        s[i] = t[i]
        x.append("".join(s))

print(len(x))
for x_i in x:
    print(x_i)

D問題

横方向と縦方向を個別に持つ
探索と削除を高速で行うためにSortedListを使う

D

from sortedcontainers import SortedList


def delete(x, y):
    if x >= 0 and y >= 0:
        wid[x].discard(y)
        hei[y].discard(x)


h, w, q = map(int, input().split())

wid = [SortedList([i for i in range(w)]) for _ in range(h)] # 横方向
hei = [SortedList([i for i in range(h)]) for _ in range(w)] # 縦方向

for _ in range(q):
    r, c = map(lambda x:int(x) - 1, input().split())
    w_i = wid[r].bisect_left(c)
    h_i = hei[c].bisect_left(r)
    if len(wid[r]) > w_i and wid[r][w_i] == c:
        delete(r, c)
    else:
        w_1 = w_2 = h_1 = h_2 = -1
        if w_i > 0:
            w_1 = wid[r][w_i - 1]
        if len(wid[r]) > w_i:
            w_2 = wid[r][w_i]
        if h_i > 0:
            h_1 = hei[c][h_i - 1]
        if len(hei[c]) > h_i:
            h_2 = hei[c][h_i]

        delete(r, w_1)
        delete(r, w_2)
        delete(h_1, c)
        delete(h_2, c)

print(sum(len(w_i) for w_i in wid))