難しかった！！！　予選の問 2 からこういうの出るのびっくり！！！

問題へのリンク

問題概要

"A", "B", "C" からなる文字列 $S$ に対して、以下の操作を繰り返すことでソートされた状態 ("A" の前には "B" や "C" がなく、"B" の前には "C" がない状態) にすることを考える。

「文字列のうち先頭から連続する何文字かを reverse する」

"A", "B", "C" からなる文字列 $S$ に対して、上記の操作を繰り返してソートされた状態にするための最小回数を $f(S)$ とする。

長さ $N$ の "A", "B", "C" のみからなる $Q$ 個の文字列 $S_{1}, \dots, S_{Q}$ が与えられるので、それぞれについて $f(S_{1}), \dots, f(S_{Q})$ の値を求めよ。

制約

$2 \le N \le 13$
$1 \le Q \le 10^{5}$

考えたこと

こういう問題を見ると、ついつい「良さげな性質」を探したくなってしまう。なにか文字列に良さげな特徴を見つけて、それを利用して言い換えると簡単に求める、という展開を期待してしまう。

でも制約を見ると $N \le 13$ となっていて、見るからに「探索してくれーーー」と言っている。良い性質を見つけようという方向性じゃなくて、むしろ全探索とかを考えた方が良さそう。

実際、長さ $N$ の "A", "B", "C" のみからなる文字列の個数は $3^{N}$ 個 ( $N!$ 個ではない) である。 $N = 13$ としても $3^{13} = 1594323$ 通りくらいなので全探索できそう！！

BFS へ

そうと決まれば BFS が良さそう。少なくとも部分点 ( $Q = 1$ ) までは愚直な BFS で大丈夫そう。

注意点として、BFS で管理する最短路配列

dp[i] ← 状態 $i$ に至るまでの最短路長

を扱うとき、添字 $i$ は単純に考えると文字列になるのだけど、それだと処理が遅くなってしまうので、文字列を整数値にエンコードしておこう。"A" を 0、"B" を 1、"C" を 2 とみなせば文字列は「三進法で表した整数」とみなせるので、それを十進法に直せば OK。

多点スタート BFS にして満点獲得

さらに、 $Q \le 10^{5}$ に対しても BFS を少し工夫すれば対応できる。通常 BFS をするとき、

与えられた文字列 $S$ を始点、
それがソートされた状態の文字列を終点として
最短経路問題を解く (by BFS)

とすると思う。でも逆転の発想をする。むしろ

ソートされた状態の文字列を始点として
すべての文字列に対する最短経路を求める

というふうにする。BFS は始点からすべての文字列への最短路が求められるのだ。ここで始点は実際には複数ありえて、

$A$ を $a$ 文字
$B$ を $b$ 文字
$C$ を $N-a-b$ 文字

をこの順に連結したものをすべて始点とする。そして BFS をすることで、全文字列 $S$ に対する $f(S)$ が求められる。

それができれば $Q$ 個の各クエリは直ちに答えられる。計算量は $O(N(3^{N} + Q))$ となる ( $3^{N}$ 通りの状態に対して $N$ 通りずつの遷移が考えられるため)。

コード

以下の実装では各操作の実施自体に $O(N)$ の計算量を要するので、実際には $O(N^{2}3^{N} + NQ)$ の計算量となっている。

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

// 文字列から整数値へ
int encode(const string &S) {
    int res = 0;
    for (auto c: S) res = res * 3 + (c - 'A');
    return res;
}

// 整数値から文字列へ
string decode(int N, int val) {
    string res = "";
    while (val) {
        res += (char)('A' + (val%3));
        val /= 3;
    }
    while (res.size() < N) res += 'A';
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;

    // すべての文字列について求めておく
    int MAX = 1;
    for (int i = 0; i < N; ++i) MAX *= 3;
    vector<int> dp(MAX+1, -1);
    queue<int> que;

    // 揃った文字列を始点にする
    for (int a = 0; a <= N; ++a) {
        for (int b = 0; a+b <= N; ++b) {
            string str = string(a, 'A') + string(b, 'B') + string(N-a-b, 'C');
            int val = encode(str);
            dp[val] = 0;
            que.push(val);
        }
    }

    // BFS
    while (!que.empty()) {
        long long val = que.front();
        que.pop();
        auto str = decode(N, val);
        for (int i = 1; i <= N; ++i) {
            string nstr = str;
            reverse(nstr.begin(), nstr.begin() + i);
            int nval = encode(nstr);
            if (dp[nval] == -1) {
                dp[nval] = dp[val] + 1;
                que.push(nval);
            }
        }
    }

    // それぞれの文字列について答える
    for (int q = 0; q < Q; ++q) {
        string S;
        cin >> S;
        cout << dp[encode(S)] << endl;
    }
}

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

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

JOI 二次予選 2021 B - パンケーキ (AOJ 0692, 難易度 7)

問題概要

制約

考えたこと

BFS へ

多点スタート BFS にして満点獲得

コード