[AtCoder] AGC 048 A – atcoder < S
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません