AtCoder Grand Contest 029 C - Lexicographic constraints

問題

　 $N(\le 2 \times 10^5)$ 個の未知の文字列 $S_1, \dots, S_N$ について、これらが辞書順に並んでおり $S_i$ の長さは $A_i$ であるとわかっているとき、文字列に含まれる文字の種類数として最小の値を求めよ。

解法

　含まれる文字の種類数 $X$ について二分探索をする。 $S_{i - 1}$ まで決まったとき次の最適な $S_i$ は $S_{i - 1}$ より辞書順で大きいもののなかで一番小さいもの。つまり使う文字を $0$ から $X - 1$ として

$A_{i - 1} \lt A_i$ のとき
0で埋めていく。
$A_{i - 1} \ge A_i$ のとき
$A_{i} + 1$ 以降の文字を消して $A_{i}$ 番目の文字を一つ大きい文字にして必要なら以降上の桁へ繰り上げていく。

　ということをやっていけば良い。これは0以外の文字についてだけstd::map等で位置と文字の関係を保持していけば $O(N\log{(\max{A})})$ で判定できる。二分探索でさらに $O(\log{N})$ かかっても十分間に合う。

反省

　「最小の値を求めよ」という問われ方をしたときに二分探索が思い浮かばないなんてことは流石になくなってきたわけだけど、判定問題に落としたところで問題が簡単になっている気がしなかった。根本的に次に来るべき文字列が辞書順最小のものということを明示的に意識できていなかったし、当然 $A_i$ 文字目を一つ大きくして繰り上げしていけばいいという考えには至らなかった。もっと問題の性質について考察をできるようになりたい。

　実装面についてはstd::mapについてイテレータで範囲を指定してeraseするやり方があることを知った。別に計算量が変わる類の話ではないだろうけどeraseで帰ってくるのが次のイテレータだから……みたいなことを考える必要がないので少しだけコーディングが速くなりそうだしこういうのは有用だと思う。std::vectorとかでもこういう指定の仕方できるわけだから当然std::mapにもあるんじゃないかと考えるべきなんだろう。

//先を全部消す
mp.erase(mp.upper_bound(A[i - 1]), mp.end());

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll N;
vector<ll> A;

bool isOK(ll x) {
    if (x == 1) {
        for (ll i = 1; i < N; i++) {
            if (A[i - 1] >= A[i]) {
                return false;
            }
        }
        return true;
    }

    //入ってないところは0ということを示す
    map<ll, ll> mp;

    for (ll i = 1; i < N; i++) {
        if (A[i - 1] < A[i]) {
            //0を入れていくだけなので何もしない
            continue;
        }

        //先を全部消す
        mp.erase(mp.upper_bound(A[i - 1]), mp.end());

        //x - 1でない位置を見つける
        ll j = A[i];
        while (mp[j] == x - 1 && j > 0) {
            mp.erase(j--);
        }

        if (j == 0) {
            //全部ダメ
            return false;
        }

        //ここの桁の値を1上げる
        mp[j]++;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    A.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }

    ll ng = 0, ok = N;
    while (ng + 1 != ok) {
        ll mid = (ng + ok) / 2;
        (isOK(mid) ? ok = mid : ng = mid);
    }
    cout << ok << endl;
}