はじめに

AtCoder Beginner Contest ( ABC ) 137 に参加。

D問題はコンテスト中に解けなかったので、公式の解説動画を見ながら自分なりにまとめてみる。

D - Summer Vacation

N件のアルバイトがあって、i 件目のアルバイトを請けると、 Ai 日後に Bi の報酬を得る。

今日から（0日目）から M 日後までに得られる最大の報酬を求める。

ただし、一日一件のアルバイトしか請けることができず、一度請けたアルバイトはその後選ぶことはできない。

参考

公式の解説動画を参考にしました。ありがとうございます。

youtu.be

条件の厳しいところから考えると良いらしい

この問題を見たとき一瞬DPかなと思ったけど、制約が

N <= 10^5
M <= 10^5

だったのでだめぽかった。

それ以外だと貪欲法で解けそうだなと考えるところまではいった。

こういう問題では条件の厳しいところから考えていくのがセオリーらしい。

この問題では考えるポイントが、一つのアルバイトに対して A と B の二つがあって、そのまま単純にアルバイト同士を比較できない。

だけどうまくやれば報酬のみでアルバイト同士を比較できるようになる。

解き方

例題（サンプル1）

N = 5
M = 3
A : 1 1 1 2 2
B : 2 3 4 1 3

M日目までに得ることができる報酬を求める。

解き方として期限の一日前から選択するアルバイトを考えていくことが重要。

サンプルだと3日目が期限なので、 2日目に選択するアルバイトを考える。

この解き方の嬉しいところは、 2日目に選択できるのが「1日後に報酬が貰えるアルバイト」のみに限定されることである。

そうすると、「1日後に報酬が貰えるアルバイト」の中から報酬が最も高いアルバイトを選択すれば良いだけになる。

次に、1日目に選択するアルバイトを考える。

1日目に選択できるのは「2日後までに報酬が貰えるアルバイト」である。

同じように「2日後までに報酬が貰えるアルバイト」の中から報酬が最も高いアルバイトを選択すれば良い。

これを繰り返すことでこの問題が解ける。

f:id:kato_robotics:20190812134947p:plain — abc137d

コード

公式の解説動画を参考に書きました。ありがとうございます。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main()
{
    int N, M;
    cin >> N >> M;
    
    // ある日まで行えるアルバイトのグループとして格納していく
    // 最大でM日まで
    vector<vector<int>> jobs(M);
 
    for(int i = 0; i < N; i++)
    {
        int A, B;
        cin >> A >> B;
 
        // AがMを超えている場合はそのアルバイトは絶対にできない
        if(A > M) continue;
        
        // M-A日まで行えるアルバイト
        jobs[M - A].push_back(B);
    }
 
    // 優先度付きキュー
    // 追加と最大値を取り出す機能を持っている
    priority_queue<int> q;
 
    long long int ans = 0;
    // 後ろから見ていく（この日まで行うことができるアルバイトグループを見ていく）
    // 例：M-1日目には、一日後に報酬がもらえるアルバイトの中で一番報酬が大きいアルバイトを選ぶ
    // また、一日後に報酬がもらえるアルバイトはM-2日目にも行えるのでそのままqueueに残しておく
    for(int i = M-1; i >= 0; i--)
    {
        // jobsのi番目の報酬の配列をpriority_queueに突っ込んでいく
        for(int b : jobs[i])
        {
            q.push(b);
        }
        if(!q.empty())
        {
            // qの最大値を取り出す
            // 現在行うことができるアルバイトの中で報酬が最大のものを選択
            ans += q.top();
            // 取り出した値を削除、一度選択したアルバイトは二度と請けられない
            q.pop();
        }
    }
 
    cout << ans << endl;
 
    return 0;
}