AGC029 C - Lexicographic constraints

本番は出場せず、Twitterで「二分探索」という単語を見てから解法を考えたため、自力で思いつけたかどうかは自信がない。
https://atcoder.jp/contests/agc029/tasks/agc029_c

問題

N個の文字列S_1, ..., S_nがある。S_iの長さはA_iであり、S_1 < S_2 < ... < S_nが成り立っている。このとき、あり得るアルファベットのサイズ(文字の種類数)として一番小さいものを求めよ。

1 <= N <= 2 * 10^5
1 <= A_i <= 10^9

解法

実現可能性はアルファベットのサイズについて単調である。つまり、アルファベットのサイズが増えることで可能だったものが不可能になることはない。
これを利用して二分探索を行うと、決められたアルファベットのサイズkについて、S_1, ..., S_nとしてあり得るものが存在するか判定すれば良いことがわかる。
先頭から貪欲に小さい文字列を割り当てていくのが最善なので、A_i < A_{i+1}ならS_iに'a' (一番小さい文字)をA_{i+1} - A_i個追加、A_i >= A_{i+1}ならS_iを切り詰めてインクリメント(最後の文字から1つ増やし、繰り上がりを左の文字へ伝播させていくこと)をしたものをS_{i+1}にすればよい。
愚直に実装するとO(A_i)時間、O(A_i)空間かかるが、A_iが大きい場合はほとんどの文字は'a'なので、'a'でない部分だけを管理すればよい。これはC++のvector (RustのVec)などで実現できる。
計算量はO(N log N)。

実装上の注意点

番兵としてS_0 = ""を用意すると楽
最小化の問題なので、サンプルが合ったからといって信用しすぎず、挙動が合っているか(デバッグプリントなどで)調べる
実装によってはk = 1のときがコーナーケースになるので気をつける

提出: Submission #3829390 - AtCoder Grand Contest 029 (Rust)

fn ok(a: &[i64], k: usize) -> bool {
    let mut cur: Vec<(_, usize)> = Vec::new();
    let mut curlen = 0;
    for &a in a {
        if curlen < a {
            curlen = a;
            continue;
        }
        // If k = 1, decrease the length and it's over.
        if k == 1 { return false; }
        curlen = a;
        // Truncate the managed string to a chars
        while let Some((x, elem)) = cur.pop() {
            if x >= a { continue; }
            cur.push((x, elem));
            break;
        }
        let mut carry = Vec::new();
        let mut pos = a - 1;
        // Increment
        loop {
            if let Some((x, elem)) = cur.pop() {
                if x == pos {
                    let c = (elem + 1) / k;
                    carry.push((x, (elem + 1) % k));
                    if c == 0 { break; }
                } else {
                    cur.push((x, elem));
                    carry.push((pos, 1));
                    break;
                }
            } else {
                carry.push((pos, 1));
                break;
            }
            if pos >= 1 { pos -= 1; }
            else { return false; }
        }
        for t in carry.into_iter().rev() { cur.push(t); }
    }
    true
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut pass = n;
    let mut fail = 0;
    while pass - fail > 1 {
        let mid = (pass + fail) / 2;
        if ok(&a, mid) {
            pass = mid;
        } else {
            fail = mid;
        }
    }
    puts!("{}\n", pass);
}

まとめ

「多倍長整数のインクリメントを実装しろ」をオブラートに包むとこういう問題になるのかな。