Greedy を考察して、さらに左右から累積和を求める！結構難しい！

類題とか

問題概要

長さ $N+1$ の数列 $A$ と、長さ $N$ の数列 $B$ が与えられます。各 $i = 1, 2, \dots, N+1$ に対して、次の値を求めよ。

数列 $A$ から $A_{i}$ を除去してできる長さ $N$ の数列 $A'$ を考えて、数列 $A'$ を適切に並び替えたときの、 $\max_{i = 1, \dots, N} (\max(A'_{i} - B_{i}, 0))$ の値の最小値

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

まずは $N+1$ 通りの値を求める問題をいきなり考えるのではなく、2 つの長さ $N$ の数列

$A_{1}, \dots, A_{N}$
$B_{1}, \dots, B_{N}$

があるとして、スコアを最小にするような $A$ の並び替え方を考えよう。また、 $B$ は小さい順にソートされていると考えて差し支えない。

A もソートしてみる

直感的には「小さい $B$ には小さい $A$ を、大きい $B$ には大きい $A$ を」割り当てるのが良さそうに思える。簡単のために $N = 2$ の場合で考えてみる。 $a \le b$ , $p \le q$ であるとして、

$A = (b, a)$
$B = (p, q)$

とする。このとき、 $a, b$ を swap してもスコアが悪化しないことが言える！！！なぜなら

$\max(b-p, 0) \ge \max(a-p, 0)$
$\max(b-p, 0) \ge \max(a-q, 0)$
$\max(b-p, 0) \ge \max(b-q, 0)$

が成り立っているから、ペア $(b, p)$ を解消することに損はないのだ。以上から、 $A$ も $B$ も小さい順にソートにして、 $\max(A_{i} - B_{i}, 0)$ の最大値を求めればよいとわかった。

クエリ処理へ

ここまでわかれば、 $N+1$ 種類の値を求めることもできる。まず $A$ と小さい順にソートしておく (index を復元できるようにしておく)。

そして $A_{i}$ を除去したときの答えは、次の 2 つの値の最大値として求められる。

$\max_{j = 1, 2, \dots, i-1} (\max(A_{j} - B_{j}, 0))$
$\max_{j = i, i+1, \dots, N} (\max(A_{j+1} - B_{j}, 0))$

これらはそれぞれ「左右からの累積 max 配列」をあらかじめ求めておくことで、高速に答えられる。この前処理は $O(N)$ でできる。解法全体としては「数列のソート」がボトルネックで $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<pair<long long,int>> A(N+1);
    vector<long long> B(N);
    for (int i = 0; i < N+1; ++i) cin >> A[i].first, A[i].second = i;
    for (int i = 0; i < N; ++i) cin >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    vector<long long> left(N+1, 0), right(N+1, 0);
    for (int i = 0; i < N; ++i) {
        left[i+1] = max(left[i], max(A[i].first - B[i], 0LL));
        right[i+1] = max(right[i], max(A[N-i].first - B[N-i-1], 0LL));
    }

    vector<int> res(N+1);
    for (int i = 0; i < N+1; ++i) {
        int id = A[i].second;
        res[id] = max(left[i], right[N-i]);
    }
    for (int i = 0; i < N+1; ++i) {
        if (i) cout << " ";
        cout << res[i];
    }
    cout << endl;
}

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

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

JOI 本選 2020 A - 長いだけのネクタイ (難易度 6)

問題概要

制約

考えたこと

A もソートしてみる

クエリ処理へ

コード