🐙

AtCoder ABC203 個人的メモ

2021/05/31に公開

Python

競技プログラミング

AtCoder

tech

所感

abc3完

A - Chinchirorin

問題文通りに場合分け。
↓の解法がとても賢いと思った。

a, b, c = map(int, input().split())

if a == b:
    print(c)
elif a == c:
    print(b)
elif b == c:
    print(a)
else:
    print(0)

B - AtCoder Condominium

制約より、NとKは9以下と分かる。
なので、二重forループですべての場合を足す。

N, K = map(int, input().split())

ans = 0
for i in range(1, N + 1):
    for j in range(1, K + 1):
        ans += 100 * i + j

print(ans)

C - Friends and Travel costs

村の数はとても多い( $10^{100}$ )ので、すべての村について考えるのは無理。
制約を見ると、友達の人数Nが $2\times 10^5$ 以下なので、これを活かしたい。
移動のコストは一定なので、ある村から別の村への移動コストはO(1)で求まる。
また、太郎君のお金が増えるのは友達がいる村を訪れたときのみ。
なので、現在地から次の友達の村までたどり着けるかを判定していけば良さそう。

from collections import defaultdict

N, K = map(int, input().split())
friends = defaultdict(int)
for _ in range(N):
    a, b = map(int, input().split())
    friends[a] += b
friends[10 ** 20] = 0

now = 0
for village in sorted(friends.keys()):
    money = friends[village]
    cal = village - now
    if K - cal < 0:
        now += K
        break
    K -= cal
    K += money
    now = village

print(now)

D - Pond

二分探索、二次元累積和

また明日

def is_ok(border: int):
    # 二次元累積和
    cumsum = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            if height[i][j] > border:
                cumsum[i + 1][j + 1] += 1
            cumsum[i + 1][j + 1] += cumsum[i + 1][j]
    for i in range(N):
        for j in range(N):
            cumsum[i + 1][j + 1] += cumsum[i][j + 1]
    # 判定
    for i in range(N - K + 1):
        for j in range(N - K + 1):
            cal = cumsum[i][j] + cumsum[i + K][j + K]
            cal -= cumsum[i + K][j] + cumsum[i][j + K]
            if cal < median_i:
                return True
    return False


N, K = map(int, input().split())
height = [list(map(int, input().split())) for _ in range(N)]

median_i = (K ** 2) // 2 + 1
ng = -1
ok = 10 ** 10
while ok - ng > 1:
    mid = (ng + ok) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

参考

中央値→二分探索

二次元累積和

所感

A - Chinchirorin

B - AtCoder Condominium

C - Friends and Travel costs

D - Pond

参考

Discussion