ABC464のPython解答（Ａ～Ｅ）

第七回日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 464）の解答等の速報的まとめ

A問題

数える

A

s = input()
e, w = 0, 0

for s_i in s:
    if s_i == "E":
        e += 1
    else:
        w += 1

print("East" if e > w else "West")

B問題

言われた通りに処理する

B

h, w = map(int, input().split())
c = [list(input()) for _ in range(h)]

while c:
    if "#" not in c[0]:
        c = c[1:]
    else:
        break

while c:
    if "#" not in c[-1]:
        c = c[:-1]
    else:
        break

while c:
    flg = True
    for c_i in c:
        if c_i[0] == "#":
            flg = False
    if flg:
        new_c = list()
        for c_i in c:
            new_c.append(c_i[1:])
        c = new_c
    else:
        break

while c:
    flg = True
    for c_i in c:
        if c_i[-1] == "#":
            flg = False
    if flg:
        new_c = list()
        for c_i in c:
            new_c.append(c_i[:-1])
        c = new_c
    else:
        break

for c_i in c:
    print("".join(c_i))

C問題

最初の色とその数をいい感じに記録して、各日ごとに差分計算をする

C

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

color = dict()
cnt = 0
lst = [list() for _ in range(m)]

for i, (a, d, b) in enumerate(data):
    if a not in color:
        color[a] = set()
        cnt += 1
    color[a].add(i)
    lst[d - 1].append((i, a, b))

for l_i in lst:
    for i, a_i, b_i in l_i:
        color[a_i].discard(i)
        if len(color[a_i]) == 0:
            cnt -= 1
        if b_i not in color:
            color[b_i] = set()
        if len(color[b_i]) == 0:
            cnt += 1
        color[b_i].add(i)

    print(cnt)

D問題

DP
$dp[i][j] = i$日目の天気が$j$の時の嬉しさの最大値

D

for _ in range(int(input())):
    n = int(input())
    s = input()
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))

    dp = [[0, 0] for _ in range(n)]
    for i, s_i in enumerate(s):
        if s_i == "S":
            if i == 0:
                dp[i][1] = -x[0]
            else:
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + y[i - 1])
                dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) - x[i]
        else:
            if i == 0:
                dp[i][0] = -x[0]
            else:
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + y[i - 1]) - x[i]
                dp[i][1] = max(dp[i - 1][0], dp[i - 1][1])

    print(max(dp[-1]))

E問題

クエリを後ろから見て、各行のどこからどこまでがどの文字になるかを調べる
ただ、そのままやると最悪ケース$H=10^6, Q=2\times10^5$で$O(HQ)\fallingdotseq 10^{11}$になり間に合わない
ただ、$H\geqq W$の時に縦横を入れ替えて計算すれば、最悪ケースが$10^8$ぐらいで済むのでぎりぎりPythonでも間に合う

E

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

if turn: h, w = w, h
data = list()
for _ in range(q):
    r, c, x = input().split()
    if turn:
        data.append([int(c) - 1, int(r) - 1, x])
    else:
        data.append([int(r) - 1, int(c) - 1, x])

lst = [list() for _ in range(h)]
next_look = 0
for r_i, c_i, x in data[::-1]:
    if next_look <= r_i:
        for i in range(next_look, r_i + 1):
            if lst[i]:
                last = lst[i][-1][1]
                if last <= c_i:
                    lst[i].append([last, c_i + 1, x])
            else:
                lst[i].append([0, c_i + 1, x])
    if c_i + 1 == w:
        next_look = max(next_look, r_i + 1)

if turn:
    ans = [list() for _ in range(w)]
    for l_i in lst:
        if l_i and l_i[-1][1] < w:
            l_i.append([l_i[-1][1], w, "A"])
        elif not l_i:
            l_i.append([0, w, "A"])
        for l, r, x in l_i:
            for j in range(l, r):
                ans[j].append(x)
    for ans_i in ans:
        print("".join(ans_i))
else:
    for l_i in lst:
        if l_i and l_i[-1][1] < w:
            l_i.append([l_i[-1][1], w, "A"])
        elif not l_i:
            l_i.append([0, w, "A"])
        for l, r, x in l_i:
            for _ in range(l, r):
                print(x, end="")
        print()