第二回 アルゴリズム実技検定 F - タスクの消化 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 F - タスクの消化

問題概要

$N$ 個のタスクがあり、 $i$ 個目のタスクは $A_i$ 日目以降に実行できる（ $A_i$ 日目に実行してもよい。なお、今日を1日目とする）。タスクを消化すると $B_i$ ポイントが得られる。

これから1日ごとに「タスクを1つ選んでそれを消化する」ことを繰り返したとき、各 $k\ (1\leqq k \leqq N)$ に対して、今日から $k$ 日間で得られる合計ポイントの最大値を答えなさい。

制約

$1\leqq N \leqq 2\times 10^5$
$1\leqq A_i \leqq N$
$1\leqq B_i \leqq 100$
$k$ 日目までに実行できるタスクは $k$ 個以上ある

解説

上のリンク先の入力例3のケースで考えてみます。与えられる入力とは形式が異なりますが、1行目を $A_i$, 2行目を $B_i$ とすることにします。

1 1 2 3 3 4
8 6 9 1 2 1

$k=1$ のときは、はじめの2つしか選べません。なので、最大値は 8 となります。

$k=2$ のときは、はじめの3つが選べます。1日目は先ほどと同じで、はじめの2つしか選べないので 8 を選ぶのがよく、2日目は 9 を選ぶのがいいですね。

$k=3$ のときは、はじめの5つのタスクから選べます。1日目は 8 を選び、2日目は 9 を選ぶといいですね。3日目は新しく選べるタスクは増えますが、ポイントが少ないので、6 を選ぶのがいいです。

$k$ 日間で得られるポイントの最大値を $m_k$ とおくことにしましょう。上で見たことからわかるのは、 $k$ 日間で得られるポイントが最大となるとき、はじめの $k-1$ 日間で得られるポイントは $m_{k-1}$ としていい、という点です。合計ポイントが最大となるには、できる限り早い段階で、最大のポイントが得られるタスクを消化したほうがいいためです。

そうすると、「 $k$ 日までに選べるタスクのうち、すでに選んだタスクを除いて、残りの中で最大のポイントのタスクを選ぶ」操作を繰り返し実行すればいいですね。このような処理に適しているのは、優先度付きキュー priority_queue です。残っているものから一番大きいものを簡単に取り出すことができます。

また、 $k$ 日の時点で選べるタスクがどれなのか把握しやすいように、 $A_i$ でソートしておくといいですね。ソートの計算が一番重くて、計算量は $O(N\log N)$ です。これなら十分間に合います。

以上を踏まえると、C++では以下のように書くことができます。コードの下に、コードの説明が続きます。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {

  int N; cin >> N;
  vector<pair<int, int>> P(N);
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b; a--;
    P[i] = make_pair(a, b);
  }
  sort(P.begin(), P.end());

  priority_queue<int> q;
  int ans = 0, i = 0;
  for (int k = 0; k < N; k++) {
    for (; i < N; i++) {
      pair<int, int> p = P[i];
      if (p.first > k) break;
      q.push(p.second);
    }
    ans += q.top(); q.pop();
    cout << ans << '\\n';
  }
  return 0;
}

前半部分では、日付とポイントをペアにして格納しています。日付は0始まりにするために1を引いています。格納した後はソートし、日付順に並び替えます。

後半ではポイントの計算をしていきます。 $k$ 日目を考えたとき、タスク $i$ が実行できるなら、ポイントをキューに追加します。タスクを全部見終わるか、 $k$ 日目ではできないタスクが出てきたら、キューに追加する操作はおしまいにします。続いて、キューから最大のポイントを取り出して、ans に追加します。こうすると、ans の値が、 $k$ 日目での最大合計ポイントとなります。