ABC473:C - Reindeer and Sleigh 2の解法メモ

問題の第一印象

• 各トナカイを「乗せる／乗せない」の 集合選択問題
• 制約付きで最大化 → まずDPを疑う

そのままDPが無理だと気づく

• 制約が$\sum_{i\notin R} P_i \ge \sum_{i\in R} W_i$という 補集合を含む形

• DPにすると

  • 状態に「力の合計」や「重さの合計」を持ちたくなる
  • しかし ($P_i$, $W_i$) が最大 ($10^{9}$)

• DPの添字が巨大になり現実的でない

👉 「DPっぽいが、そのままでは破綻する」

発想の転換：補集合を消す

全体の力の合計を使う：

\sum_{i\notin R} P_i
= \sum_{i=1}^N P_i - \sum_{i\in R} P_i

これを元の条件に代入すると：

\sum_{i=1}^N P_i \ge \sum_{i\in R}(P_i + W_i)

問題の正体が見える

ここで問題は次の形に変わる：

• 予算：(B = $\sum P_i$)
• 各トナカイのコスト：($c_i = P_i + W_i$)
• 目的：選ぶ個数（＝乗せるトナカイの数）を最大化

価値がすべて 1 のナップサック問題

なぜDPではなく貪欲なのか

重要な観察

• 最大化したいのは「価値の合計」ではなく 個数
• 各トナカイの価値は区別されない（全部同じ）

つまり：

• 同じ個数なら 合計コストが小さい方が常に有利
• 高コストのものを、より低コストのものと交換しても悪化しない

交換法が成立する

貪欲が正当化される理由

この問題の貪欲は：

ナップサックDPの
「価値がすべて同じ」特殊ケース

DPの状態遷移が
「コストの小さい順に詰める」
1通りに収束するため、DPを書く必要がない。

実装方針

1. (B = $\sum P_i$) を計算
2. 各 ($c_i = P_i + W_i$) を配列に入れる
3. ($c_i$) を昇順ソート
4. 小さい順に足していき、合計が (B) を超えない最大個数を数える

今回のまとめ

• DPを発想する
• 「価値が全部同じ」と気づいた瞬間に貪欲へ降格
• 貪欲は DP の“状態空間が潰れた特殊ケース”

次に同系統を見抜くチェック

• 最大化したいのは「個数」か？
• 価値に差はあるか？
• 同じ個数なら「軽い方が必ず得」か？

👉 Yes が並んだら 貪欲候補

解答

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;

    for (int i = 0; i < T; i++) {
        int N;
        cin >> N;
        long long W, P;
        long long B = 0;
        long long sum = 0;
        long long index = 0;
        vector<long long> S(N, 0);

        for (int j = 0; j < N; j++) {
            cin >> W >> P;
            S[j] = W + P;
            B += P;
        }

        sort(S.begin(), S.end());

        while (sum + S[index] <= B && index < N) {
            sum += S[index];
            index++;
        }

        cout << index << '\n';
    }

    return 0;
}