問題概要

文字列 $S$ が与えられる。文字列 $S$ に以下の操作を最小回数行うことで、辞書順で $S$ > "atcoder" となるようにせよ。

$S$ 中の連続する 2 文字を swap する

(このテストケースが $T$ 個与えられる)

制約

$1 \le T \le 100$
$1 \le |S| \le 1000$

解法 (1)：探索

T = "atcoder" とする。そもそも S > T なら答えは 0 となる。そうでないとする。

まず、操作は次のようなものだと考えてよいことに注意する。ある添字 i が存在して、i < j かつ S[ j ] > T[ i ] となる j に対して、S[ j ] を S[ i ] まで持ってくるようなもののみを考えればよい。

swap 後に「S[ i ] < T[ i ] となる最小の i」をどのようにするかで場合分けして考えることにする。このとき

S の最初の i 文字は T と一致
S[ i ] < T[ i ]

という 2 つの条件を満たすことになる。ただし、S の最初の i 文字は最初から T の最初の i 文字と一致する必要がある。その前提下で i を固定したとき、i < j かつ S[ j ] > T[ i ] を満たすような最小の j を求める。そして j - i が swap 回数となる。これを各 i について試して、その最小値を求めれば OK。計算量は $O(|S|^{2})$ となる。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<29;
const string T = "atcoder";
int solve(const string &S) {
    if (S > T) return 0;

    int res = INF;
    auto first = [&](int i) -> int {
        int j = i;
        for (; j < S.size(); ++j) if (S[j] > T[i]) break;
        return (j < S.size() ? j - i : INF);
    };
    for (int i = 0; i < S.size() && i < T.size(); ++i) {
        res = min(res, first(i));
        if (S[i] < T[i]) break;
    }
    return (res < INF/2 ? res : -1);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string S;
        cin >> S;
        cout << solve(S) << endl;
    }
}

解法 (2)：考察で計算量を減らす

そもそも不可能な場合は「すべての文字が "a"」という場合しかない。たとえば S = "aaaaaaab" のようなケースだったとしても、"b" を先頭まで持ってくれば S > T となるからだ。

そして S = "aaaaaaaaaaz" のようなケースであれば、"z" を先頭まで持ってこなくても 2 文字目まで持ってきて "azaaaaaaaaa" とすれば S > T となる。逆に 2 文字目までは持ってこないと S > T とはならない。

このような考察から整理して考える。例外的なケースを先に処理しておく。

S の文字がすべて "a" の場合は、答えは -1
最初から S > T ならば、答えは 0
そうでないとすると、S の先頭の文字は "a" であるはずである。2 文字目が "a" でないときは、先頭と 2 文字目を入れ替えればよいだけなので、答えは 1

これらのケースを除外すると、S の先頭の 2 文字は "aa" となることがわかる。このとき、操作として「"a" 以外の文字を先頭または 2 文字目まで持ってくる」というものだけを考えれば良い、と言える。よって、

S の先頭から見ていって、文字目 (0-indexed) が "a" でなかったとする。そのような各に対して次のように考える
- S[ k ] > "t" ならば、 $K - 1$ 回
- S[ k ] <= "t" ならば、 $K$ 回

計算量は $O(|S|)$ となる。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<29;
const string T = "atcoder";
int solve(const string &S) {
    if (S > T) return 0;
    int res = INF;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == 'a') continue;
        if (i == 1) res = 1;
        else if (S[i] > 't') res = min(res, i - 1);
        else res = min(res, i);
    }
    return (res < INF ? res : -1);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string S;
        cin >> S;
        cout << solve(S) << endl;
    }
}