ABC318をPythonで（A~E）

THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）
URL：ABC318

A問題

問題文の通りにすればよい

A

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

ans = 0
for i in range(1, n + 1):
    if (i - m) % p == 0:
        ans += 1

print(ans)

ただし、計算で求めることもできる。

A別解

n, m, p = map(int, input().split())
print((n - m) // p + 1)

B問題

いもす法など高速化の方法はあるが、愚直にやっても時間に間に合う。

B

field = [[0] * 110 for _ in range(110)]

n = int(input())
for _ in range(n):
    a, b, c, d = map(int, input().split())
    for i in range(a, b):
        for j in range(c, d):
            field[i][j] += 1

ans = 0
for f_i in field:
    for f_j in f_i:
        ans += (f_j > 0)

print(ans)

C問題

金額がかかる方から順に、d日間の合計金額とpのうち安いほうを採用する。

C

n, d, p = map(int, input().split())
f = list(map(int, input().split()))
f.sort(reverse=True)
ans = 0
for i in range(0, n, d):
    ans += min(p, sum(f[i:i + d]))

print(ans)

D問題

D

n = int(input())
edge = []
for i in range(n - 1):
    e_i = list(map(int, input().split()))
    edge.append([0] * (i + 1) + e_i)

dp = [0] * (1 << n)
for bit in range(1 << n):
    for i in range(n):
        if bit >> i & 1: continue
        for j in range(i + 1, n):
            if bit >> j & 1: continue
            dp[bit + (1 << i) + (1 << j)] = max(dp[bit + (1 << i) + (1 << j)], dp[bit] + edge[i][j])

print(max(dp))

E問題

(iとkの間にあるjになりうるものの個数)
x（iとその左にある同じ数の個数）x（jとその右にある同じものの個数）

E

n = int(input())
a = list(map(int, input().split()))
d = dict()
for i, a_i in enumerate(a):
    if a_i not in d:d[a_i] = []
    d[a_i].append(i)

ans = 0
for val in d.values():
    for i in range(len(val) - 1):
        ans += (val[i + 1] - val[i] - 1) * (i + 1) * (len(val) - i - 1)

print(ans)