ABC322をPythonで（A~E）

AtCoder Beginner Contest 322
https://atcoder.jp/contests/abc322

A問題

全探索をする

A

n = int(input())
s = input()

for i in range(n - 2):
    if s[i:i+3] == "ABC":
        print(i + 1)
        exit()

print(-1)

B問題

接頭辞が違ったら答えに+2
接尾辞が違ったら答えに+1

B

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

f1 = s == t[:n]
f2 = s == t[-n:]

ans = 0
if not f1:ans += 2
if not f2:ans += 1
print(ans)

C問題

最終日から数えていくとよい
花火を打ち上げる日をsetで管理するとやりやすい

C

n, m = map(int, input().split())
a = set(map(lambda x:int(x) - 1, input().split()))

day = [0] * n
for i in range(n - 1, -1, -1):
    if i not in a:
        day[i] += day[i + 1] + 1

for d_i in day:
    print(d_i)

D問題

各ポリオミノを座標で管理する
そのうえで次のことを行う
1、a, b, cを平行移動させて4ｘ4に収まるか全探索
2、aは回転させずにbやcを90度回転させる

D

def make():
    res = []
    for i in range(4):
        for j, s_i in enumerate(input()):
            if s_i == "#":
                res.append((i, j))
    return res

a = make()
b = make()
c = make()

def turn(x):
    res = []
    for i, j in x:
        res.append((j, 4 - i))
    return res

# 平行移動
def solve(a, b, c):
    for a_i, a_j in [(i, j) for i in range(-4, 4) for j in range(-4, 4)]:
        for b_i, b_j in [(i, j) for i in range(-4, 4) for j in range(-4, 4)]:
            for c_i, c_j in [(i, j) for i in range(-4, 4) for j in range(-4, 4)]:
                field = [[0] * 4 for _ in range(4)]
                flag = True
                for i, j in a:
                    if 0 <= i + a_i < 4 and 0 <= j + a_j < 4 and field[i + a_i][j + a_j] == 0:
                        field[i + a_i][j + a_j] += 1
                    else:
                        flag = False
                for i, j in b:
                    if flag and 0 <= i + b_i < 4 and 0 <= j + b_j < 4 and field[i + b_i][j + b_j] == 0:
                        field[i + b_i][j + b_j] += 1
                    else:
                        flag = False
                for i, j in c:
                    if flag and 0 <= i + c_i < 4 and 0 <= j + c_j < 4 and field[i + c_i][j + c_j] == 0:
                        field[i + c_i][j + c_j] += 1
                    else:
                        flag = False
                if flag:
                    print("Yes")
                    exit()
    return False

# ミノが16個ちょうどでないときは不適
if len(a) + len(b) + len(c) != 16:
    print("No")
    exit()

# b,cを回転させるパターンを全探索
for _ in range(4):
    for _ in range(4):
        solve(a, b, c)
        c = turn(c)
    b = turn(b)

print("No")

E問題

dp問題
k=1のときはナップザック問題とおなじ
ただしkが変わるためそのままでは出来ない
つねにk=5としてやってもできなくはないだろうが、自分は違う方法を取った

i番目(0-index)のパラメーターに(p+1)**iを掛けて、それらの総和をとる
するとこの和と各パラメーターが一対一対応を取る

これを利用することでdpが解ける

E

n, k, p = map(int, input().split())

Pattern = (p + 1) ** k
# dp[i] = iの時の最小コスト
# i = x_0 + x_1*(p+1) + x_2*(p+1)**2 + ...

dp = [INF] * Pattern
dp[0] = 0
for _ in range(n):
    c, *a = map(int, input().split())
    for now in range(Pattern - 1, -1, -1):
        lst = []
        i = now
        for _ in range(k):
            lst.append(i % (p + 1))
            i //= (p + 1)
        for j, a_i in enumerate(a):
            lst[j] += a_i
        to = 0
        for j, l_i in enumerate(lst):
            to += min(l_i, p) * (p + 1) ** j
        dp[to] = min(dp[to], dp[now] + c)

print(dp[-1] if dp[-1] < INF else -1)