パナソニックプログラミングコンテスト AtCoder ABC195 個人的メモ

2 min read読了の目安(約2100字

所感

ac2完
abc195

A - Health M Death

問題文通りにモンスターの体力HMの倍数か判定

M, H = map(int, input().split())

if H % M == 0:
    print("Yes")
else:
    print("No")

B - Many Oranges

みかんの重さは整数でなくても良いので,選んだみかんの重さは全て等しいと考える
こう考えると,Wを個数で割った値がA以上B以下になっているかを判定すればおk

A, B, W = map(int, input().split())
INF = 10 ** 18

W *= 1000
small = INF
big = 0
num = 1
while W / num >= A:
    if A <= W / num <= B:
        small = min(small, num)
        big = max(big, num)
    num += 1

if small == INF or big == 0:
    print("UNSATISFIABLE")
else:
    print(small, big)

C - Comma

10^3以上の数1つにつきコンマが1つある
同様に10^6,10^9,10^{12},10^{15}で判定すればおk
N\leqq 10^{15}なので10^{15}までで良い

N = int(input())

ans = 0
res = 1
while True:
    res *= 10 ** 3
    if N >= res:
        ans += N - res + 1
    else:
        break

print(ans)

D - Shipping Center

考察はあってたのに実装バグらせてた

各クエリで以下を処理する

  1. 使える箱を小さい順に見ていく
  2. その箱に入れることができる荷物を列挙する
  3. それらの内,最も価値と重さが大きいものを箱に入れる
  4. 以上を全ての使える箱で繰り返す
N, M, Q = map(int, input().split())
baggage = [list(map(int, input().split())) for _ in range(N)]
X = list(map(int, input().split()))

for _ in range(Q):
    L, R = map(lambda x: int(x) - 1, input().split())

    tmp_baggage = list(baggage)
    ans = 0
    # 1.
    available_box = sorted(X[:L] + X[R + 1:])
    for i in available_box:
        candidate = []
        trash = []
        # 2.
        while tmp_baggage:
            w, v = tmp_baggage.pop()
            if i >= w:
                candidate.append([w, v])
            else:
                trash.append([w, v])
        # 3.
        if candidate:
            candidate.sort(key=lambda candidate: candidate[1])
            _, v = candidate.pop()
            ans += v
        tmp_baggage = trash + candidate

    print(ans)