ABC391をPythonで（A～F）

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

A問題

文字を逆方向のものに変換する

A

s = input()
ans = ""
for s_i in s:
    ans += {"N":"S", "S":"N", "E":"W", "W":"E"}[s_i]

print(ans)

B問題

全探索するだけ

B

def check(x, y):
    for i in range(m):
        for j in range(m):
            if s[i + x][j + y] != t[i][j]:
                return False
    return True


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

for i in range(n - m + 1):
    for j in range(n - m + 1):
        if check(i, j):
            exit(print(i + 1, j + 1))

C問題

i番目のハトがいる巣の番号と各巣にいる鳩の数を移動のたびに変え、変わった巣が2羽の境界を越えたら答え用の変数を増減させる

C

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

Pigeon = [i for i in range(n)]
count = [1 for _ in range(n)]
ans = 0

for _ in range(q):
    com = list(map(int, input().split()))
    if com[0] == 1:
        p, h = com[1:]
        p -= 1
        h -= 1
        ind = Pigeon[p]
        count[ind] -= 1
        if count[ind] == 1:
            ans -= 1
        Pigeon[p] = h
        count[h] += 1
        if count[h] == 2:
            ans += 1
    else:
        print(ans)

D問題

i番目のブロックが消えるタイミングは、下からの個数が一致するブロックの中で一番上に配置されるものの高さと一致する
ない列の有無を確認しつつ一番高いブロックを調べて、あとから各クエリと比較する

D

from heapq import heappop, heapify

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

area = [list()for _ in range(w)]
for i, (x, y) in enumerate(block):
    x -= 1
    area[x].append([y, i])

for i in range(w):
    heapify(area[i])

INF = 10 ** 10
time = [INF] * n
while True:
    flag = True
    t = 0
    lst = list()
    for i in range(w):
        if area[i]:
            t_i, ind = heappop(area[i])
            lst.append(ind)
            t = max(t, t_i)
        else:
            flag = False
    if flag:
        for l_i in lst:
            time[l_i] = t
    else:
        break

for _ in range(int(input())):
    t, a = map(int, input().split())
    if time[a - 1] <= t:
        print("No")
    else:
        print("Yes")

E問題

DFS
今見ている3数がAそのものだったらA[i]を、そうでないなら1つ深さを進める
それぞれで変化なしで得られる数字と変化させるのに必要な変化数を返す

E

n = int(input())
a = input()

def calc(depth=0, ind=0):
    if depth == n:
        return a[ind], 1
    else:
        num1, cnt1 = calc(depth + 1, 3 * ind)
        num2, cnt2 = calc(depth + 1, 3 * ind + 1)
        num3, cnt3 = calc(depth + 1, 3 * ind + 2)

        if num1 == num2 == num3:
            return num1, cnt1 + cnt2 + cnt3 - max(cnt1, cnt2, cnt3)
        elif num1 == num2:
            return num1, min(cnt1, cnt2)
        elif num1 == num3:
            return num1, min(cnt1, cnt3)
        elif num2 == num3:
            return num2, min(cnt2, cnt3)

    return 0, 0

print(calc()[1])

F問題

重複に気を付けつつ大きいほうからK個ぐらいを生成して調べる

F

from heapq import heappop, heappush

n, k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

def add(i, j, k):
    global check, lst
    if i < n and j < n and k < n and (i, j, k) not in check:
        check.add((i, j, k))
        heappush(lst, (-(a[i] * b[j] + b[j] * c[k] + c[k] * a[i]), i, j, k))


lst = []
check = set()
ans = 0
add(0, 0, 0)
for _ in range(k):
    ans, ind_a, ind_b, ind_c = heappop(lst)

    add(ind_a + 1, ind_b, ind_c)
    add(ind_a, ind_b + 1, ind_c)
    add(ind_a, ind_b, ind_c + 1)

print(-ans)