ABC461のPython解答（A～D）

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

A問題

そのまま

A

a, d = map(int, input().split())
print("Yes" if a <= d else "No")

B問題

Bを並び替えて対応をわかりやすくする

B

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

cnt = 0
lst = [(b_i, i) for i, b_i in enumerate(b, 1)]
lst.sort()
for a_i, (_, i) in zip(a, lst):
    cnt += a_i == i

print("Yes" if cnt == n else "No")

C問題

まず各種類の中で一番価値が高い宝石を並べて、その中で高いもの$M$個を取る。
そのあと、選ばなかった宝石の中から残りの$K - M$個を価値の高い順に取る。

C

n, k, m = map(int, input().split())
jewel = [list(map(int, input().split())) for _ in range(n)]

ans = 0

d = dict()
box = list()
for c, v in jewel:
    if c in d:
        if d[c] < v:
            box.append(d[c])
            d[c] = v
        else:
            box.append(v)
    else:
        d[c] = v

lst = sorted(d.values(), reverse=True)
for i, v in enumerate(lst):
    if i < m:
        ans += v
    else:
        box.append(v)

box.sort(reverse=True)
ans += sum(box[:k - m])

print(ans)

D問題

累積和をいい感じに利用して求める

D

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

for i in range(h - 1):
    for j in range(w):
        s[i + 1][j] += s[i][j]

for i in range(h):
    for j in range(w - 1):
        s[i][j + 1] += s[i][j]

def calc(a, b, c):
    if a == 0:
        return s[b][c]
    else:
        return s[b][c] - s[a - 1][c]

ans = 0
for x1 in range(h):
    for x2 in range(x1, h):
        d = {0:1}
        for y in range(w):
            val = calc(x1, x2, y)
            if val - k in d:
                ans += d[val - k]
            if val not in d:
                d[val] = 0
            d[val] += 1

print(ans)