AtCoder Regular Contest 044 D - suffix array

ARC 044 に参加しました。 B が難しかったせいか, C の部分点取るだけで結構上位にいけました。いや上位とっても解けないと意味無いですけど。
D は言われてみるとかなり簡単だったので C 捨てて考えても良かったかも。

問題

arc044.contest.atcoder.jp

解法

辞書順最小の文字列を求めたいので, A[1] 番目の文字は 'A' に決定します。

また, その後の文字 A[i] については, できれば A[i-1] と同じ文字にして できるだけ辞書順最小を目指したいわけですが, どうしても A[i] 番目の文字を A[i-1] 番目の文字より大きい文字にしなければならないこともあります。どういう時にこうしなければならないかというと, A[i]+1 番目から先の文字列の辞書順が, A[i-1]+1 番目から先の文字列の辞書順より小さい場合です。

具体例を挙げます。例えばサンプルのひとつ目, 7 5 1 3 6 2 4 という数列を考えます。

まず 7 番目の文字は 'A' です。次に 5 番目の文字を決定したいですが, 7+1 番目からの文字列よりも 5+1 番目からの文字列のほうが辞書順で大きいことが順列を見るとわかる(8 は順列にないですが必ず辞書順最小になるので順列を 8 7 5 1 3 6 2 4 としておく)ので 5 番目の文字は 7 番目と同じ 'A' で良いです。

次に 1 番目の文字を決定したいですが, 5+1 番目からの文字列よりも 1+1 番目からの文字列のほうが辞書順で大きいことが順列を見るとわかるので 1 番目の文字は 5 番目と同じ 'A' で良いです。

3 番目の文字も同様に 'A' です。

6 番目の文字を決定したいです。 3+1 番目からの文字列のほうが 6+1 番目の文字列よりも辞書順で大きいです。この場合は, 6 番目の文字を 'A' にしてしまうと, suffix array の順序が 3 と 6 で逆転してしまうので, 6 番目の文字は 'B' にしなければなりません。

以下同様です。これをやっていくことで, 答えは ABACABA であるとわかります。

const int MAXN = 1000100;
char ans[MAXN];
int pos[MAXN], A[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        A[i]--;
        pos[A[i]] = i;
    }
    pos[N] = 0;
    char c = 'A';
    ans[A[1]] = c;
    for (int i = 2; i <= N; i++) {
        if (pos[A[i-1]+1] > pos[A[i]+1]) {
            if (c == 'Z') {
                cout << -1 << endl;
                return 0;
            }
            c++;
        }
        ans[A[i]] = c;
    }
    for (int i = 0; i < N; i++) cout << ans[i];
    cout << endl;
    return 0;
}