[JOI精進録] 難易度7「パンケーキ」(JOI2020/2021 二次予選B)

悪名高いやつ
2105ms/2500msなので想定解法じゃないかも

問題リンク

atcoder.jp

問題概要

よいパンケーキ文字列を以下で定義する。
・A、B、Cからなる文字列で、ASCIIコードで昇順にsortしたものと一致する (例「ABC」「AAAB」「CCCC」)
沢山のクエリが与えられる。クエリは ・文字列が与えられる。先頭から文字分ひっくり返す操作を最小何回行うことで一致させられるか
である。

解説

AC解法 (100/100点)

がちっちゃい。そしてよいパンケーキ文字列は高々パターンである。全列挙できそうだ。
ということでBFSを終点から行い、始点を入力すればクエリに高速に答えることができる。
unordered_mapじゃないと通らなかった。

ACコード

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

int main(){
  int n,q; cin >> n >> q;
  unordered_map<string,int> M;
  for (int i(0);i <= n;++i) for (int k(i);k <= n;++k) {
    string s;
    for (int l(0);l < i;++l) s+="A";
    for (int l(i);l < k;++l) s+="B";
    for (int l(k);l < n;++l) s+="C";
    queue<string> que; que.emplace(s);
    while(!que.empty()){
      auto& a = que.front(); int d = M[a];
      for (int l(2);l <= n;++l){
        reverse(a.begin(),a.begin()+l);
        if (M[a]==0) M[a] = d+1,que.emplace(a);
        reverse(a.begin(),a.begin()+l);
      }
      que.pop();
    }
  }
  string s;
  while(q--){
    cin >> s;
    if (M[s]<=2&&is_sorted(s.begin(),s.end())) cout << 0 << '\n';
    else cout << M[s] << '\n';
  }
  cout.flush();
}

sort済みかを判定するプログラムが余計についてる。距離を+1してクエリに-1して答えればよかったが忘れてた
とは書いたが試したらの+1はきついらしくTLEした。

提出結果

atcoder.jp