パナソニックプログラミングコンテスト(ABC195 D - Shipping Center)【Python解答例】

AtCoder Beginner Contest195のD - Shipping CenterについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder

AtCoder Beginner Contest 195 D - Shipping Center

D - Shipping Center

問題文

1 から N の番号がついた N 個の荷物と、1 から M の番号がついた M 個の箱があります。
荷物 i の大きさは Wi で、価値は Vi です。
箱 i には大きさが Xi 以下の荷物を入れることができます。
1 つの箱に 2 つ以上の荷物を入れることはできません。
Q 個のクエリが与えられます。各クエリでは 2 つの整数 L,R が与えられるので、次の問題を解いてください。

問題：M 個の箱のうち、箱 L,L+1,…,R の R−L+1 個の箱が使えなくなってしまいました。 残りの箱の中に同時に入れることができる荷物の価値の合計の最大値を求めてください。

制約

・1≤N≤50
・1≤M≤50
・1≤Q≤50
・1≤Wi≤10^6
・1≤Vi≤10^6
・1≤Xi≤10^6
・1≤L≤R≤M
・入力は全て整数

解答例

n, m, q = map(int,input().split())

WV = []
for i in range(n):
    array = list(map(int,input().split()))
    WV.append(array)
WV.sort(key=lambda x:x[1], reverse=True) # 価値Vの降順にソート

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

Q = []
for i in range(q):
    array = list(map(int,input().split()))
    Q.append(array)

# クエリ分だけループ
for i in range(q):  # i番目のクエリ
    ans = 0
    X_copy = X[:] # リストXをコピー
    del X_copy[Q[i][0]-1:Q[i][1]]   # LからRの箱を消去
    X_copy.sort()   # 箱の大きさを昇順でソート
    for wv in WV:   # 荷物のループ(Vが大きい順)
        for j in range(len(X_copy)):    #箱のループ(大きさが小さい順)
            if wv[0] <= X_copy[j]:  # 探索中の箱に荷物が入れば
                ans += wv[1]        # 価値Viを足して
                X_copy.pop(j)       # 荷物を入れた箱を消去
                break
    print(ans)

解説

それぞれ大きさがWi、価値がViの荷物がN個と、M個の箱があります。
箱iには大きさXi以下の荷物をひとつだけいれることができるという初期条件があります。
Q個のクエリがあり、各クエリでは箱LからRが使えなくなる条件が与えられ、残った箱に入れることができる荷物の価値の最大値をそれぞれ答える問題です。

各クエリごとに箱を消去し、残った箱の小さいものから、できるだけ価値の大きい荷物を貪欲に入れていく方針で進めればOKでした。

上記の方針があるので標準入力はWとVだけVの昇順（大きい順）にソートしました。

あとは各クエリ毎のループをまわします。
リストXは何度も使用するのでクエリ毎にコピーしました。
クエリの条件から使用できない箱をX_copyから消去し、箱の小さい順にソートします。

価値の大きい荷物から、小さい箱の順にループを回していき、入れることができる組み合わせを見つけたら順次荷物を入れていきます。
荷物を入れるたびに価値をansに足していき、入れた箱はリストX_copyから消去しました。

この2重ループを抜けたら価値の合計であるansを出力することを繰り返せばACをとれました。

問題を見ときはDPかと思いましたが、貪欲法で解ける問題でした。
コンテスト中でも解けるように学習を続けていきたいです。

ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com