ABC195D - Shipping Center

考え方

以下2点がポイント．

• 制約がユルイので，マッチングを全探索できる（bisectは必要ない．3重ループで間に合う．）
• 貪欲法で解ける

貪欲法の考え方は，2パターンある．

1. 「箱」を順番に見る：「後ステップに大きい箱を残す」ことは，「それより小さい箱を残すこと」の上位互換（選択肢がより多くなる）である．よって，小さい箱から順に考えればよい．各ステップで見ている箱には，なるべく価値が高い品物を入れて行けば良い．
2. 「品物」を順番に見る：全ての箱に品物が収まっている状況で，もし，より価値の高い品物を入れられる箱があれば，箱の中身を交換したほうが価値の合計が大きくなる．よって，はじめに価値ゼロの品物が箱に入っているとして，価値の大きい品物から順に置き換えていくのが最適になる（価値の大きい品物から見ていくと，価値ゼロ以外の箱は置き換わらない）．各ステップでは，なるべく小さい箱に入れたほうが，後の選択肢が増えるので有利．

個人的には箱を順番に見るほうがわかりやすい．品物を順にみるのは，「価値を大きいものをスキップした方が，残りの組み合わせで有利になることはないか？」という疑問で混乱した（仮にスキップして残りを全てマッチングして，最後にスキップした品物を置き換えればより価値が高くなるので，このようなことはない）．

回答例

【「箱」を順番に見る】

N, M, Q = map(int, input().split())
VW = []
for _ in range(N):
    w, v = map(int, input().split())
    VW.append((v, w))
VW.sort(reverse = True)

X = list(map(int, input().split()))

for _ in range(Q):
    L, R = map(int, input().split())
    X2 = X[:L - 1] + X[R:]
    X2.sort()
    seen = [False] * N
    ans = 0
    for x in X2:
        for i, (v, w) in enumerate(VW):
            if not seen[i] and w <= x:
                seen[i] = True
                ans += v
                break

    print(ans)

【「品物」を順番に見る】

N, M, Q = map(int, input().split())
VW = []
for _ in range(N):
    w, v = map(int, input().split())
    VW.append((v, w))
VW.sort(reverse = True)

X = list(map(int, input().split()))

for _ in range(Q):
    L, R = map(int, input().split())
    X2 = X[:L - 1] + X[R:]
    X2.sort()
    seen = [False] * len(X2)
    ans = 0
    for v, w in VW:
        for i, x in enumerate(X2):
            if not seen[i] and w <= x:
                seen[i] = True
                ans += v
                break

    print(ans)

メモ

• if seen[i]:continueとしたほうが早い．
• PyPyよりPythonの方が早い．