こんにちは。今日も解説記事を書きます。

今回扱うのは、今朝布団の中で軽い気持ちで開いたら泥沼に嵌ってしまった400点問題です。沼ったよって言ったら周りの人も分かるって言ってたので令BC400の中ではそれなりに難しい部類と思われます(difficulty は水底くらいでした。みんなすごい)。

これ解けてないし400点最難関でいいよ
— ヒトデマン (@wa1t_sush1) 2020年5月1日

問題

D - Summer Vacation

$N$ コの日雇いバイトがあり、それぞれ最大1回働ける。
1日に1件しかバイトできない(給料が払われるまでの期間に他のバイトをすることは可能)。
$i$ 番目のバイトをすると $A_i$ 日後に $B_i$ の給料が入る。
今日から $M$ 日後までに入る給料の総和の最大値を求めよ。
$1$ $\leq$ $N,\ M$ $\leq 10^{5}$

解法

1日に1件しか働けないので、毎日どのバイトをやると良いかを考える。
$d$ 日目には $A > M-d$ のバイトをしても支払いが $M$ 日目に間に合わないので $A\leq M-d$ であるようなバイトが候補となる。
そこで $d$ を降順に考えると最初 $(M - 1)$ 日目は $A\leq 1$ のバイトだけが候補となり、 $(M - 2)$ 日目では $A\leq 2$ を満たすバイトが候補となる。
これより、 $d$ 日目で新しく $A==M-d$ であるようなバイトを順に追加していくとその日やる価値のあるバイト候補リストを構築できる。
リスト内から報酬が最大の案件を取り出せば良い。この操作は priority_queue というデータ構造を用いる¹。

実装

解説記事だし流石にREPマクロ排除しました()。

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll n, m;
    cin >> n >> m;

    // mem[x] :バイトした日から x 日後に報酬がもらえる仕事の集合. 値は報酬額
    vvll mem(m + 1);
    ll a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (a > m) continue; // 最速で始めても M 日目に支払いが間に合わないバイトは無視
        mem[a].push_back(b);
    }

    // que : その日入れられる仕事の報酬リスト
    // mem を参照してギリ M 日目に間に合うバイトの報酬額を que に追加していく
    priority_queue<ll> que;
    ll res = 0;
    for (int d = m - 1; d >= 0; d--) {
        // mem[m - d] : d 日目に始めたらちょうど M 日目に報酬が降ってくる仕事の集合(b はその個々の報酬額)
        for (auto b : mem[m - d]) que.push(b);
        if (!que.empty()) {
            res += que.top();
            que.pop();
        }
    }
    cout << res << endl;
    return 0;
}

感想

今回は報酬の支払い日について $M$ 日後までという締め切りがある問題でしたが、こういった期限が絡む問題は締め切りが近い後ろ側から見ると貪欲に解けたり(c.f. 区間スケジューリング問題)、この問題のように実行可能な要素の集合を良い感じに構築できたりします。切羽詰まってるときに重要度が等しい複数のタスクがあるとき期限が近いほうから処理する感覚に近い気がします。
まぁ令BC400だし貪欲でしょと考えたらドツボに嵌ったのですが。点数見て偏見で解くの良くないかも(´ー｀)

それではまた！