AtCoder AGC 022 A - Diverse Word (茶色, 300 点)

ある程度探索でゴリ押した。

• 問題へのリンク

問題概要

英小文字のみからなり、どの 2 文字も互いに相異なる文字列を「多彩」であると呼ぶこととする。多彩な文字列 が与えられる。以下の条件を満たす文字列の中で最も辞書順が小さいものを求めよ。

• よりも辞書順で大きい
• 多彩である

存在しない場合は "-1" を出力せよ。

制約

• 
• は多彩な文字列

考えたこと

まず が 26 文字未満ならば、「使用していない文字」があるはずである。そのうちの最小の文字を c として、S + c が答えとなる。 が 26 文字である場合は、すべての英小文字が 1 回ずつ用いられているはずである。この場合はある i に対して、

(最初の i 文字は S と同じもの) + (S[i] より大きく、それ以前に登場していない最小の文字)

が答えとなるはずである。そのような i が大きければ大きいほどよい。つまり、

• S[i] より大きく、S.substr(0, i) の中に登場していない文字

というものが存在するような最大の i に対して、上記のものを求めればそれが答えとなる。唯一の例外として、"zyxwvu...a" に対しては、そのような i が存在しないため "-1" を出力する。

コード

ここでは上記の i を全探索する方針で書いた。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    string INF(26, 'z');
    string S;
    cin >> S;
    auto first = [&](int left, int right, char mi) -> char {
        for (char c = mi; c <= 'z'; ++c) {
            bool exist = false;
            for (int i = left; i < right; ++i) if (S[i] == c) exist = true;
            if (!exist) return c;
        }
        return '?';
    };
    if (S.size() < 26) {
        cout << S + first(0, S.size(), 'a') << endl;
    }
    else {
        string res = INF;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == 'z') continue;
            char c = first(0, i, S[i]+1);
            if (c != '?') chmin(res, S.substr(0, i) + c);
        }
        cout << (res < INF ? res : "-1") << endl;
    }
}