はまやんはまやんはまやん

hamayanhamayan's blog

国士無双 [yukicoder No.548]

https://yukicoder.me/problems/no/548

解説

https://yukicoder.me/submissions/192890

追加する文字を全探索する。
'a'~'z'の文字を追加して、大丈夫なら答えとする。

あとは、ある文字列が条件を満たすかをチェックする関数(check関数)を作るだけなのだが、これは色々な実装方法がありそう。
自分は、以下の手順で実装した。

1. 各文字の文字数をカウントする
2. 'a'~'k'の文字数だけ取り出し、vectorに入れる
3. そのvectorをソートする
4. vectorの要素数が13じゃないなら return false (文字種類は13種である必要があるため)
5. 最初の12個が1であり、最後が2であるなら return true そうでないなら return false

bool check(string s) {
    map<char, int> m;
    fore(c, s) m[c]++;

    vector<int> v;
    rep(j, 0, 13) if (m['a' + j]) v.push_back(m['a' + j]);
    sort(v.begin(), v.end());

    if (v.size() != 13) return 0;

    int ok = 1;
    rep(i, 0, 12) if (v[i] != 1) ok = 0;
    if (v[12] != 2) ok = 0;

    if (ok) return 1;
    return 0;
}
//---------------------------------------------------------------------------------------------------
vector<char> solve(string S) {
    vector<char> ans;

    rep(i, 0, 13) {
        char c = 'a' + i;
        if (check(S + c)) ans.push_back(c);
    }

    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    string S; cin >> S;
    
    auto ans = solve(S);

    if (ans.size() == 0) printf("Impossible\n");
    else fore(i, ans) printf("%c\n", i);
}