問題概要

長さ $N$ の整数列 $a_{1}, \dots, a_{N}$ が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。

与えられた数列において、最大で $K$ 箇所まで値を書き換えることができる。書き換えた数列の退屈さとして考えられる最小値を求めよ。

制約

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

考えたこと

「最大値の最小化」なので、ごく自然に二分探索で解けるのだけど、とても鮮やかな別解があるのでそれで解いてみる。ちょうど Session3 の G 問題と同じように解く！！

drken1215.hatenablog.com

まず、数列をランレングス圧縮したときの、各区間の長さの列を $l_{1}, \dots, l_{p}$ とする。このとき

$i$ 番目の要素に対して $k$ 回の操作を行うと、スコアは $L / (k + 1)$ になる

という風に考えることができる。各要素に対する操作の合計値が $K$ となるように操作を行ったときの、「各要素のスコアの最大値」を最小にする問題だと言える。これは次のような Greedy で求められる。

その時点でスコアが最大となっている要素に対して操作を行っていく

これはもっと簡単に、各要素に対する

元の長さ, 1 回の操作を行ったときの長さ, 2 回の操作を行ったときの長さ, ...

を全部混ぜたベクトル v を考えて、それをまとめてソートしてしまえばよい。その $K$ 番目の値が答えとなる。なお、元の長さが $L$ であるような系列においては、 $L$ 回以上の操作を行う必要がないことから、v に挿入する値は、最大でも $L$ 個となる。 $L$ の合計値は $N$ なので、v のサイズは $O(N)$ となる。

よって $O(N \log N)$ で解くことができた。

コード

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<int> v;
    for (int i = 0; i < N;) {
        int j = i;
        while (j < N && a[j] == a[i]) ++j;
        int len = j - i;
        for (int k = 0; k <= len; ++k) v.push_back(len / (k+1));
        i = j;
    }
    sort(v.begin(), v.end(), greater<int>());
    cout << max(v[min(K, (int)v.size()-1)], 1) << endl;
}

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

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

CPSCO2019 Session4 D - Boring Sequence (400 点設定)

問題概要

制約

考えたこと

コード