AGC 048 | A - atcoder < S

問題

https://atcoder.jp/contests/agc048/tasks/agc048_a

考えたこと

$S$のスワップ回数での条件整理が大事。答えが-1, 0, 1以上の場合で条件をわけて考える。

(1) -1の場合

どのようにしてもatcoderより辞書順が小さい場合。atcoderは先頭がaなのでaのみの文字列だとatcoderより辞書順が常に小さくなってしまう。

(2) 0の場合

すでに辞書順の場合は交換しなくてよい。

(3) 以上の場合

前述の(1), (2)の条件より文字列は以下の条件を満たす。

• 先頭は必ずaである。
• a以外のものが含まれている。

先頭から走査し、最初に現れるa以外の文字を$C$とし、位置を$POS$(0-indexed)とするとすると、$C$をindex=1の位置まで移動するにはPOS - 1必要である。
その移動した状態で辞書順になっていればそれが最適解。なっていなければ$S[0]$と$S[1]$を交換すれば辞書順になるので$POS$が答えである。

コード

実装時のTips

• 文字列aとbの辞書順の比較は a < b でできる
• iとjの位置の文字のスワップは swap(s[i], s[j]) でできる

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  int T;
  cin >> T;
  string tar = "atcoder";  // target
  for (int i = 0; i < T; i++) {
    string s;
    cin >> s;
    // 初期状態ですでに辞書順になっているか
    if (tar < s) {
      cout << 0 << endl;
      continue;
    }

    // すべてaか調べる
    bool isOnlyA = true;
    int pos = -1;
    for (int j = 0; j < s.size(); j++) {
      char c = s[j];
      if (c != 'a') {
        isOnlyA = false;
        pos = j;
        break;
      }
    }
    if (isOnlyA) {
      cout << -1 << endl;
      continue;
    }

    // どこかにaでないのがある. その場合はそれをs[1]のとまで入れ替えて辞書順か調べる
    for (int j = pos; j > 1; j--) {
      swap(s[j], s[j - 1]);
    }
    if (tar < s) {
      cout << pos - 1 << endl;
    } else {
      cout << pos << endl;
    }
  }
}

参考

• https://atcoder.jp/contests/agc048/editorial/197