ABC195 D問題を解く - 競技プログラミング悪戦苦闘日記

不具合を埋め込み時間が足りずに解けなかったD問題をふりかえりつつ、解説します。

1 から N の番号がついた N 個の荷物と、1 から M の番号がついた M 個の箱があります。
荷物 i の大きさは $W_i$ で、価値は $V_i$ です。
箱 i には大きさが $X_i$ 以下の荷物を入れることができます。
1 つの箱に 2 つ以上の荷物を入れることはできません。
Q 個のクエリが与えられます。各クエリでは 2 つの整数 L, R が与えられるので、次の問題を解いてください。
問題：M 個の箱のうち、箱 L, L + 1,…, R の R−L+1 個の箱が使えなくなってしまいました。残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。

直感的に、価値が最大の荷物を選んで、できるだけ大きさがピッタリの箱を選んでいけば最適になるはずと思いました。
証明は公式の解説にお任せします。

荷物のリストは価値の大きいものから順に並び替えて、残った箱のリストはサイズが小さい順に並び替えて、for文で全量ループさせました。

幸いにも箱の数、荷物の数、問題の数が最大で50なので、できるだけピッタリの箱を選ぶ時に二分探索をすることもなく、解けました。

コードは以下のようになりました。

N, M, Q = list(map(int, input().split()))
wv_arr = []
for _ in range(N):
    w, v = list(map(int, input().split()))
    wv_arr.append([w, v])
# 価値が大きい順に並び替える
wv_arr = sorted(wv_arr, key=lambda x: x[1], reverse=True)
x_arr = list(map(int, input().split()))

for _ in range(Q):
    l, r = list(map(int, input().split()))
    r_x_arr = []
    ans = 0

    # 箱を取り除く
    for i, x in enumerate(x_arr):
        if l-1 <= i <= r-1:
            continue
        r_x_arr.append(x)
    r_x_arr.sort()

    # 埋まってる箱に目印をつけるための配列
    rx_memo = [0 for _ in range(len(r_x_arr))]

    for wv in wv_arr:
        for i, rx in enumerate(r_x_arr):
            if wv[0] <= rx and rx_memo[i] == 0:
                ans += wv[1]
                rx_memo[i] = -1
                break
    print(ans)