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

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

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

難しかった!!! 予選の問 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;
    }
}