ABC390をPythonで（A～E）

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

A問題

実際に入れ替えた配列を作って比較する

A

a = list(map(int, input().split()))

for i in range(4):
    b = [i for i in range(1, 6)]
    b[i], b[i + 1] = b[i + 1], b[i]
    if a == b:
        exit(print("Yes"))

print("No")

B問題

比が同じかを順番に調べる
割ると誤差が怖いので掛け算で比較する

B

n = int(input())
a = list(map(int, input().split()))

ans = "Yes"
if n >= 3:
    for i in range(1, n - 1):
        if a[i] ** 2 != a[i - 1] * a[i + 1]:
            ans = "No"

print(ans)

C問題

長方形になる範囲を調べて、その範囲内に白く塗られたマスがあるか調べる

C

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

ax, ay, bx, by = 1000, 1000, 0, 0
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ax = min(ax, i)
            bx = max(bx, i)
            ay = min(ay, j)
            by = max(by, j)

ans = "Yes"
for i in range(ax, bx + 1):
    for j in range(ay, by + 1):
        if s[i][j] == ".":
            ans = "No"

print(ans)

D問題

組み合わせを全通り導出して数える
すべての袋に入れるパターンを考えると間に合わないので、無駄な場所に入れないように制限をかける

D

n = int(input())
a = list(map(int, input().split()))

ans = set()

def dfs(lst, last, count):
    global ans
    if count == n:
        b = 0
        for l_i in lst:
            b ^= l_i
        ans.add(b)
    else:
        for i in range(min(last + 1, n)):
            new_lst = lst.copy()
            new_lst[i] += a[count]
            if i == last:
                dfs(new_lst, last + 1, count + 1)
            else:
                dfs(new_lst, last, count + 1)


dfs([0] * n, 0, 0)
print(len(ans))

E問題

各ビタミンでdpをしてカロリーごとの摂取量を求めておく
そのあと摂取量を基準に二分探索でカロリーを超えていないか確かめる

E

from bisect import bisect_left

def calc(lst):
    dp = [0] * (x + 1)
    for a, c in lst:
        for i in range(x, c - 1, -1):
            dp[i] = max(dp[i], dp[i - c] + a)
    return dp

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

vitamin = [list(), list(), list()]
for _ in range(n):
    v_i, a_i, c_i = map(int, input().split())
    vitamin[v_i - 1].append([a_i, c_i])

vitamin1 = calc(vitamin[0])
vitamin2 = calc(vitamin[1])
vitamin3 = calc(vitamin[2])

def calc2(target):
    v_1 = bisect_left(vitamin1, target)
    v_2 = bisect_left(vitamin2, target)
    v_3 = bisect_left(vitamin3, target)
    return v_1 + v_2 + v_3

ok, ng = 0, 10 ** 9 + 10
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if calc2(mid) <= x:
        ok = mid
    else:
        ng = mid

print(ok)