【競技プログラミング】AtCoder Beginner Contest 195_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

1. 荷物を価値の降順でソートする。
2. 各クエリに対して、使用可能な箱のリストを作成する。
3. 使用可能な箱を大きさでソートする。
4. 価値の高い荷物から順に、入れられる最小の箱に割り当てていく。
5. 割り当てが終わったら、その時点での価値の合計を出力する。

解法手順

1. 入力を受け取り、荷物のリストを作成する。
2. 荷物を価値の降順でソートする。
3. 各クエリに対して以下の処理を行う：
   • 使用可能な箱のリストを作成する（L-1番目までとR番目以降の箱）。
   • 使用可能な箱を大きさでソートする。
   • 価値の高い荷物から順に以下の処理を行う：
     • 二分探索を使用して、荷物が入る最小の箱を見つける。
     • 適切な箱が見つかったら、その箱を使用済みとしてリストから削除し、価値を合計に加算する。
     • 使用可能な箱がなくなったら処理を終了する。
   • 合計価値を出力する。

ACコード

ac.py

import bisect  # 二分探索のためのモジュールをインポート

# 1. 入力を受け取り、荷物のリストを作成する
N, M, Q = map(int, input().split())  # N: 荷物の数, M: 箱の数, Q: クエリの数
item = [list(map(int, input().split())) for _ in range(N)]  # 荷物のリスト（重さと価値）
X = list(map(int, input().split()))  # 箱のサイズのリスト

# 2. 荷物を価値の降順でソートする
item.sort(reverse=True, key=lambda x: x[1])  # 価値の降順でソート

# 3. 各クエリに対して処理を行う
for _ in range(Q):
    L, R = map(int, input().split())  # クエリの入力（L番目からR番目までの箱は使用不可）
    
    # 使用可能な箱のリストを作成する
    w = X[:L-1] + X[R:]  # L-1番目までとR番目以降の箱
    w.sort()  # 箱を大きさでソート
    
    res = 0  # 合計価値を初期化
    
    # 価値の高い荷物から順に処理
    for weight, value in item:
        # 二分探索を使用して、荷物が入る最小の箱を見つける
        idx = bisect.bisect_right(w, weight)
        
        if idx > 0 and w[idx-1] == weight:
            # 荷物の重さと同じ大きさの箱がある場合
            w.remove(w[idx-1])
            res += value
        elif idx < len(w):
            # 荷物が入る箱がある場合
            w.remove(w[idx])
            res += value
        else:
            # 荷物が入る箱がない場合は次の荷物へ
            continue
        
        # 使用可能な箱がなくなったら処理を終了
        if not w:
            break
    
    # 合計価値を出力
    print(res)