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

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

JOIG 2021 D - 展覧会 2 (AOJ 0704) (2Q, 難易度 6)

AtCoder JOI JOIG JOI難易度6 競プロ典型90問とその類題 二分探索 最大値の最小化 N個からK個を選ぶ設定の問題 N個のペア値の問題 数直線上のN点の問題 Greedy 最大スコア 考察：順序を工夫して解く 【問題集】二分探索の入門 AOJ ソート:前処理 最適化問題 NoviSteps2Q

「競プロ典型 90 問 001 - Yokan Party」とよく似た問題！

前提知識

問題概要

N 枚の絵が一直線上に順に並んでいます。 i 枚目の絵は座標 X_{i} の位置にあり、その価値は V_{i} です。

今これらの絵から M 枚の絵を選びます。このとき次の制約を満たさなければなりません。

  • どの 2 枚の絵も、距離が D 以上離れなれければならない

「選んだ M 枚の絵の価値の最小値」として考えられる最大値を求めてください。ただし制約条件を満たすように M 枚を選ぶことが不可能である場合は -1 と出力してください。

制約

  • 1 \le M \le N \le 10^{5}

判定問題に帰着する

今回の問題は「最小値を最大化してください」という問題になっています。そのように「最大値を最小化」や「最小値や最大化」な問題では、二分探索法が有効なことが多いですね。まずは今回の問題を判定問題化＊してみましょう！

選んだすべての絵の価値が x 以上となるように、 M 枚の絵を選べるかどうかを判定してください。ただしどの 2 枚の絵の間隔も D 以上離す必要があります。

x が小さいときは "Yes" になります (ならないことも) し、 x が大きいときは "No" になります。二分探索法によってその境界が特定できます。

この判定の問題の答えが "Yes" となる最大の x が答えです。

具体的には次のコードのようにできます。絵の間隔としてありうる最大値を Y として、二分探索法の反復回数は O(\log Y) 回となります。

long long low = -1, high = 1LL<<30;
while (high - low > 1) {
    long long x = (low + high) / 2;
    if (絵の価値をすべて x にできる) low = x;
    else high = x;
}
return x;

　

判定問題を解く

まずは絵を左から順に並び替えておきます。

このとき判定問題を解くのは、次のような Greedy 解法でできます。絵を左から順に見ていき、

  • 前回選んだ絵から距離が D 以上離れている
  • 価値が x 以上ある

という条件をともに満たす最左の絵を選ぶことを繰り返していけばよいでしょう。そのように絵を選んでいき、 M 枚選べたら "Yes"、 M 枚に達しないうちに絵の右端に達してしまったら "No" と判定できます。

具体的な処理については、下のコードを参考にしましょう。判定問題を解くのは O(N) の計算量でできます。

よって全体として O(N (\log N + \log Y)) の計算量で解けます。

コード

そもそも M 枚を選べない場合もあります。その場合であっても下のコードのように low = -1 と初期化しておくことで統一的に解けます。

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<40;

int main() {
    long long N, M, D;
    cin >> N >> M >> D;
    vector<long long> X(N), V(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> V[i];

    // 一直線上に左から順に並び替える (ここでは id を並び替える)
    vector<int> ids(N);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) {
        return X[i] < X[j];
    });

    // 二分探索
    long long low = -1, high = INF;
    while (high - low > 1) {
        long long x = (low + high) / 2;

        int con = 0;  // 選んだ枚数
        long long prev = -INF;  // 最後に選んだ絵の位置
        for (auto id : ids) {
            if (X[id] - prev >= D && V[id] >= x) {
                ++con; 
                prev = X[id];
            }
        }
        if (con >= M) low = x;
        else high = x;
    }
    cout << low << endl;
}