けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 048 A - atcoder < S (緑色, 300 点)

単純な探索でも解けるし、考察で計算量を減らすこともできそう。

問題概要

文字列  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 の先頭から見ていって、 K 文字目 (0-indexed) が "a" でなかったとする。そのような各  K に対して次のように考える
    • 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;
    }
}