けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 二次予選 2021 C - イベント巡り (AOJ 0693, 難易度 8)

JOI JOI予選・二次予選 JOI難易度8 AOJ AtCoder DP DP値を利用して状態復元 二分探索 二分探索:lower_bound 座標圧縮 数直線上のN点の問題 Greedy:後によいものを残す・今が良いほど未来も良い

これはアレだ！！！　 DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。

問題概要

2 つの町 (1 と 2) がある。 N 個のイベントがあって、それぞれ町 P_{i} において発生し、時刻 S_{i} に始まり時刻 S_{i} + 1 に終了する。

イベント i に参加するためには、時刻 S_{i} の瞬間に町 P_{i} にいることが必要かつ十分である。そして時刻 S_{i}+1 の瞬間には他の町へと向かってよい。

さて、2 つの町の間を移動するのに要する時間は、その時点までに参加したイベントの個数を n として、 D + K \times n となる (イベントに参加すればするほど、移動時間が増加していく)。

参加できるイベントの個数の最大値を求めよ。なお、時刻 0 からイベントに参加するが、参加時にはいずれの町から出発してもよい。

制約

  • 1 \le N \le 2 \times 10^{5}
  • 1 \le D, S_{i} \le 10^{12}
  • 0 \le K \le 10^{12}

考えたこと

一見すると O(N^{2}) かかる DP に見えるやつだった。

  • dp[i][j] ← i 番目のイベント (どちらの町なのかも込み) に参加するとして、それまでに j 個のイベントに参加していたとした場合の最適値

こうすると O(N^{2}) かかるように見えるのだけど、よく考えると添字 j は要らないという。

  • dp[i] ← i 番目のイベントに参加するとしたときの、それまでのイベント参加回数の最大値

そして今回は「配る DP」の方が書きやすい！！！「貰う DP」でも書けるんだけど、その場合は「二分探索」とかが必要になる (公式解説参照)。

配る DP はこんな感じに書ける。

  • i 番目のイベントから町を移動せずに参加できる最直近のイベントを j としたとき chmax(dp[j], dp[i] + 1)
  • i 番目のイベントから町を移動して参加できる最直近のイベントを k としたとき chmax(dp[k], dp[i] + 1)
    • このときの移動時間は dp[i] を用いて表せる

なお、DP の遷移順は「イベントの開始時刻の早い順」にするようにする。計算量は、色々工夫すれば O(N \log N) になる。

気になる点

今回の DP の肝は、DP の遷移を決める部分それ自体に dp[i] という値を利用する点だと思う。それはフクロモモンガでも同様。

通常の DP は、予め、どの添字からどの添字へと遷移すべきかが決まる。でも今回の DP は、dp[i] という値が決まるまでは、頂点 i からどの頂点へと遷移すべきかが決まらないのだ。

そしてもう一つ気になることは、「イベント i 時点では最適でなかったとしてもそれが結果的に最終的には最適解になる可能性」だ。この大前提を満たさないと DP は崩壊する。しかしよく考えると、イベント i 時点までのイベント回数が少ない解が、最終的によりよくなることはあり得ない。よって今回の解法で大丈夫。

コード

ここでは楽するために、dp 配列を map でやった。座標圧縮でやるのが本筋だとは思う。

#include <bits/stdc++.h>
using namespace std;
using Event = pair<long long, int>; // time, which

void chmax(int &a, int b) { if (a < b) a = b; }

int main() {
    long long N, D, K;
    cin >> N >> D >> K;
    vector<vector<long long>> time(2);
    vector<Event> events({Event(0, 0), Event(0, 1)});
    for (int i = 0; i < N; ++i) {
        long long P, S;
        cin >> P >> S;
        --P;
        time[P].push_back(S);
        events.emplace_back(S, P);
    }
    for (int i = 0; i < 2; ++i) sort(time[i].begin(), time[i].end());
    sort(events.begin(), events.end());

    map<Event, int> dp;
    dp[Event(0, 0)] = dp[Event(0, 1)] = 0;
    for (auto e: events) {
        int p = e.second, cur = dp[e];

        // そのままの町で
        auto it = lower_bound(time[p].begin(), time[p].end(), e.first + 1);
        if (it != time[p].end()) chmax(dp[Event(*it, p)], cur + 1);

        // 移動
        long long need = D + K * cur;
        it = lower_bound(time[1-p].begin(), time[1-p].end(), e.first + 1 + need);
        if (it != time[1-p].end()) chmax(dp[Event(*it, 1-p)], cur + 1);
    }
    int res = 0;
    for (auto it: dp) chmax(res, it.second);
    cout << res << endl;
}