ABC331をPythonで（A～E）

大和証券プログラミングコンテスト2023（AtCoder Beginner Contest 331）

A

問題文のとおりに実装

A

M, D = map(int, input().split())
y,m,d = map(int, input().split())
d += 1
if d > D:
    d = 1
    m += 1
    if m > M:
        y += 1
        m = 1

print(y, m, d)

B

dpで実装した

B

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

dp = [0] + [float("inf")] * (n + 12)
for i in range(1, n + 12):
    if i >= 6:
        dp[i] = min(dp[i], dp[i - 6] + s)
    if i >= 8:
        dp[i] = min(dp[i], dp[i - 8] + m)
    if i >= 12:
        dp[i] = min(dp[i], dp[i - 12] + l)

print(min(dp[n:]))

C

大きい順に累積和をとる
そのあと値の境目になったところを辞書に記録して答えを出す

C

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

b = sorted(a) + [float("inf")]
c = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    c[i] += b[i] + c[i + 1]

d = dict()
last = -1
for i, b_i in enumerate(b):
    if last < b_i:
        d[last] = c[i]
        last = b_i

ans = [d[a_i] for a_i in a]
print(*ans)

D

黒の数を2次元累積和で計算する
クエリは包除原理で計算
公式解説がわかりやすい

D

n, q = map(int, input().split())
p = [input() for _ in range(n)]

data = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if p[i][j] == "B":
            data[i][j] += 1

for i in range(n):
    for j in range(n - 1):
        data[i][j + 1] += data[i][j]
for i in range(n - 1):
    for j in range(n):
        data[i + 1][j] += data[i][j]

def calc(x, y):
    if x < 0 or y < 0:
        return 0
    res = 0
    if x >= n and y >= n:
        res += data[-1][-1] * (x // n) * (y // n)
    if x >= n:
        res += data[-1][y % n] * (x // n)
    if y >= n:
        res += data[x % n][-1] * (y // n)
    
    return res + data[x % n][y % n]

for _ in range(q):
    a, b, c, d = map(int, input().split())
    print(calc(c, d) - calc(c, b - 1) - calc(a - 1, d) + calc(a - 1, b - 1))

E

各副菜に対して最大になる主菜を求める
ただし、愚直に行うと間に合わない

1. 主菜を値段の高い順にソート
2. 高いほうから順に取り合わせが問題がないか調べる
3. 問題がなかったらそれで決定して次から調べないようにする

これをすると$L+M$回調べるだけで全通り求めることが出来る

E

n, m, l = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
NG = [set() for _ in range(n)]
for _ in range(l):
    c, d = map(lambda x:int(x) - 1, input().split())
    NG[c].add(d)

A = [(a_i, i) for i, a_i in enumerate(a)]
A.sort(reverse=True)

lst = [i for i in range(m)]
d = [-float("inf")] * m
for a_i, i in A:
    new_list = []
    for j in lst:
        if j not in NG[i]:
            d[j] = a_i
        else:
            new_list.append(j)
    lst = new_list

print(max(d_i + b_i for d_i, b_i in zip(d, b)))