弱かった。。。

問題概要

$N$ 個の正の整数 $A_1, A_2, \dots, A_N$ が与えられる。

文字列の列 $S_1, S_2, \dots, S_N$ であって

$S_i$ の文字数が $A_i$ である
辞書式順序で $S_1$ < $S_2$ < $\dots$ < $S_N$

を満たすもののうち、登場文字数の最小値を求めよ。

制約

$1 \le N \le 2 × 10^{5}$
$1 \le A_i \le 10^{9}$

考えたこと

$S$ が狭義単調増加だったら、"a" の個数だけで行けるので 1 だな

$S$ が狭義単調減少だったら、うまく "b" を織り交ぜれば 2 で行けるな

といったあたりを手を動かしながら考えていた。S の列のとりかたは概ね Greedy で良さそうだけど

S = (3, 2, 3, 2, ...)

といったインスタンスに対して

"aaa", "ab", "aba",

となって次を考えたときに、"ba" がいいのか "ac" がいいのかよくわからない。2 文字で済むなら前者、2 文字じゃ不可能なら後者。となると、予め「何文字使う」というのを fix したくなって、二分探索がバッチリ当てはまる。

すなわち、

x 文字以下でできるか？

という判定問題を Greedy に解けばいい。ただし、ナイーブにやると文字数が 10⁹ になって爆発する。

そこで以下のような圧縮された世界で考える。

aaabccddd -> {(a, 3), (b, 1), (c, 2), (d, 3)}

この手の圧縮は名称があったと思うけど忘れてしまった。。。ともかくこの圧縮された世界で実装する必要がある。

注意点として、

A[ i ] < A[ i + 1 ] となるときは、'a' を後ろに付け加える
A[ i ] >= A[ i + 1 ] となるとき、文字列を A[ i + 1 ] 文字になるまで pop_back して、文字列を x 進法数値とみなして 1 増やす

ということをするわけだが、ここで後者の処理をナイーブに pop_back で実装すると計算量が一見ヤバく見える。でも実際は、push_back する回数が総合的に高々 N 回なので、pop_back する回数も高々 N 回になる。

全体として、計算量は $O(N \log{N})$ になる。

#include <iostream>
#include <vector>
using namespace std;

using pll = pair<long long, long long>;

void normalize(vector<pll> &nums) {
    if (nums.size() > 1) {
        if (nums[nums.size()-1].first == nums[nums.size()-2].first) {
            nums[nums.size()-2].second += nums[nums.size()-1].second;
            nums.pop_back();
        }
    }
}

void zouka(vector<pll> &nums) {
    if (nums.back().second == 1) {
        nums.back().first += 1;
    }
    else {
        nums.back().second--;
        nums.push_back(pll(nums.back().first+1, 1));
    }
    normalize(nums);
}

int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    long long low = 0, high = N+1;
    while (high - low > 1) {
        long long mid = (low + high) / 2;
        
        vector<pll> nums;
        nums.push_back(pll(0, a[0]));
        bool ok = true;
        for (int i = 1; i < N; ++i) {
            if (a[i-1] < a[i]) nums.push_back(pll(0, a[i] - a[i-1]));
            else {
                long long sum = 0;
                while (nums.size() > 0 && sum + nums.back().second <= a[i-1] - a[i]) {
                    sum += nums.back().second;
                    nums.pop_back();
                }
                nums.back().second -= a[i-1] - a[i] - sum;

                if (nums.back().first == mid-1) {
                    if (nums.size() == 1) {
                        ok = false;
                        break;
                    }
                    long long num = nums.back().second;
                    nums.pop_back();
                    zouka(nums);
                    nums.push_back(pll(0, num));
                }
                else zouka(nums);
            }
            normalize(nums);
        }

        if (ok) high = mid;
        else low = mid;
    }
    cout << high << endl;
}

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

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

AtCoder AGC 029 C - Lexicographic constraints (黄色, 700 点)

問題概要

制約

考えたこと