ABC332をPythonで（A~D）

AtCoder Beginner Contest 332

A問題

問題文の通りに書く

A

n, s, k = map(int, input().split())
sums = 0
for _ in range(n):
    p, q = map(int, input().split())
    sums += p * q

if sums >= s:
    print(sums)
else:
    print(sums + k)

B問題

丁寧にシミュレーションをする

B

k, g, m = map(int, input().split())

a = b = 0
for _ in range(k):
    if a == g:
        a = 0
    elif b == 0:
        b = m
    else:
        if a + b <= g:
            a += b
            b = 0
        else:
            b -= g - a
            a = g

print(a, b)

C問題

ロゴ入りを$i$枚買ったとしてシミュレーションをする
途中で破綻しなかったらそれが正解

C

n, m = map(int, input().split())
s = input()

def solve(t):
    a, b = m, t
    for s_i in s:
        if s_i == "0":
            a, b = m, t
        elif s_i == "1":
            if a > 0:
                a -= 1
            elif b > 0:
                b -= 1
            else:
                return False
        else:
            if b > 0:
                b -= 1
            else:
                return False
    return True

for i in range(n + 1):
    if solve(i):
        print(i)
        exit()

D問題

まず縦横のスワップは他方に影響を与えない
よって縦横でスワップの局面と回数と全て調べて
Bと一致できるか全探索する

D

from collections import deque

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

def calc(n):
    q = deque()
    q.append([i for i in range(n)])
    check = set()
    check.add((i for i in range(n)))
    cnt = 0
    # print(n, s, t)
    data = dict()
    while q:
        new_q = deque()
        while q:
            a = q.popleft()
            if cnt not in data:
                data[cnt] = []
            data[cnt].append(a)
            for i in range(n - 1):
                a_i = a[::]
                a_i[i], a_i[i + 1] = a_i[i + 1], a_i[i]
                if tuple(a_i) not in check:
                    check.add(tuple(a_i))
                    new_q.append(a_i)
        q = new_q
        cnt += 1

    return data

d1 = calc(h)
d2 = calc(w)

def check(p1, p2):
    for i in range(h):
        for j in range(w):
            if a[p1[i]][p2[j]] != b[i][j]:
                return False
    return True

INF = float("inf")
ans = INF
for k1, v1 in d1.items():
    for k2, v2 in d2.items():
        if any(check(p1, p2) for p1 in v1 for p2 in v2):
            ans = min(ans, k1 + k2)

print(-1 if ans >= INF else ans)