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

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

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

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

類題とか

drken1215.hatenablog.com

問題概要

長さ  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;
}