AtCoder Grand Contest 029 C - Lexicographic constraints

C - Lexicographic constraints

問題概要

$ N \leq 2 \times 10^5 $個の文字列があり，$ i$番目の文字列の長さが$ a_i (\leq 10^9)$であるとき，全ての文字列を辞書順にするために必要な最小の文字の種類数を求める．

解法概要

二分探索で答えの候補を決めてからその文字数で条件を達成できるか判定する． 1つの文字列の長さが最大[tex:{\displaystyle 10⁹}] なので，これをいかに処理するかがミソ． 多くの文字が辞書順で最小の文字であるはずなので，それ以外の文字が入る部分をmapで管理すれば効率が良さそう．

文字列は0-indexedとする．また，使える文字の種類をx種類とする． mapで「0番目に小さい文字以外の文字が入っている場所のindex」を管理する．今，$ a_i$について見ているとしたら，mapを$ a_{i-1}$についての「0番目に小さい文字以外の文字が入っている場所のindex」から$ a_i$についての当該情報に更新する処理をすれば良い． mapの中の要素の削除処理は実装注意．私の回答では，一旦vectorのto_eraseに削除すべき要素のキーを溜めている．

• if $ a_{i-1} \lt a_i $
  • mapの中でキーjが$ j >= a_i$となる要素を削除する．
• else if $ a_{i-1} = a_i$
  • 文字列の末尾に当たるキーから順にmapを$ a_i-1, a_i-2, \cdots, 0$ と見ていき，最初に文字を変えられる (x-1番目の文字を使っていない) ところを変える．このとき，末尾側にx-1番目の文字が続いている場合はそのキーはmapから削除する．
  • 文字列を後ろから先頭まで見終わっても文字を変えられない場合は，その字数で条件を達成できない．
• else
  • 文字列の後ろ側に当たるキーから順にmapを$ a_i-1, a_i-2, \cdots, 0$ と見ていき，最初に文字を変えられるところを変える．このとき，後ろ側が 文字列を後ろから先頭まで見終わっても文字を変えられない場合は，その字数で条件を達成できない．
  • mapの中でキーjが$ j >= a_i$となる要素を削除する．

ソースコード

#include<iostream>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;

bool check(int n, vector<int> a, int x) {
    map<int, int> mp;
    mp[a[1]-1] = 0;

    for(int i=1;i<=n;++i) {
        vector<int> to_erase;
        if(a[i-1] < a[i]) {
            for(auto itr=mp.begin();itr!=mp.end();++itr) {
                if(itr->first >= a[i]) {
                    to_erase.push_back(itr->first);
                }
            }
        } else if(a[i-1] == a[i]) {
            bool added = false;
            for(int j=a[i]-1;j>=0;--j) {
                if(mp.find(j) == mp.end()) {
                    if(x == 1) return false;
                    mp[j] = 1;
                    added = true;
                    break;
                } else if(mp[j] != x-1) {
                    ++mp[j];
                    added = true;
                    break;
                } else {
                    to_erase.push_back(j);
                }
            }
            if(!added) return false;
        } else {
            bool added = false;
            for(int j=a[i]-1;j>=0;--j) {
                if(mp.find(j) == mp.end()) {
                    if(x == 1) return false;
                    mp[j] = 1;
                    added = true;
                    break;
                } else if(mp[j] != x-1) {
                    ++mp[j];
                    added = true;
                    break;
                } else {
                    to_erase.push_back(j);
                }
            }
            if(!added) return false;

            for(auto itr=mp.begin();itr!=mp.end();++itr) {
                if(itr->first >= a[i]) {
                    to_erase.push_back(itr->first);
                }
            }
        }

        for(int e: to_erase) mp.erase(e);
    }

    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n+1, 0);
    for(int i=1;i<=n;++i) cin >> a[i];
    
    int ng = 0, ok = 300000;
    while(ok-ng > 1) {
        int mid = (ok + ng) / 2;
        if(check(n, a, mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    cout << ok << endl;
}

所感

新年初AC． 実装が結構大変だった．