[AtCoder] AGC 048 A – atcoder < S

2020年12月12日

問題

方針

\( S \) が 'a’ だけの文字からなるとき、’atcoder’ \( < S\) とあることはありません。また、’atcoder’ '\(  < S \) であるとき操作を行う必要がありません。

操作を行う場合は、’b’ から 'z’ までの文字を考えればよく、\( S \) の最も左側にある各文字を \( S \) の先頭から \( 7 \) 番目までに移動するという操作の中に最小値が含まれます。

コード

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

string S;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

void solve() {
    if ("atcoder" < S) {
        cout << "0\n";
        return;
    }
    bool flag = true;
    int n = S.length();
    int v[26]{};
    fill(v, v + 26, n);
    for (int i = 0; i < n; i++) {
        if (S[i] != 'a') {
            chmin(v[S[i] - 'a'], i);
            flag = false;
        }
    }
    if (flag) {
        cout << "-1\n";
        return;
    }
    int best = n;
    for (int i = 1; i < 26; i++) {
        for (int j = 0; j < min(7, v[i]); j++) {
            string T = S;
            swap(T[j], T[v[i]]);
            if ("atcoder" < T) {
                chmin(best, v[i] - j);
            }
        }
    }
    cout << best << "\n";
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> S;
        solve();
    }
    return 0;
}