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

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

AtCoder AGC 029 C - Lexicographic constraints (700 点)

弱かった。。。

問題へのリンク

問題概要

 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 に解けばいい。ただし、ナイーブにやると文字数が 109 になって爆発する。

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

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