寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #B - パンケーキ (Pancake)

JOI 2020/2021 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#B - パンケーキ (Pancake)

atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#B - パンケーキ (Pancake)
https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_b
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int n,q;
  cin>>n>>q;
  int num=1;
  for(int i=0;i<n;i++){
    num*=3;
  }
  vector<int> dist(num,1e9+7);
  queue<int> que;
  for(int i=0;i<num;i++){
    int fl=0;
    bool tf=true;
    int i2=i;
    for(int j=0;j<n;j++){
      if(i2%3<fl){
        tf=false;
      }
      fl=max(fl,i2%3);
      i2/=3;
    }
    if(tf){
      dist[i]=0;
      que.push(i);
    }
  }
  while(!(que.empty())){
    int u=que.front();
    que.pop();
    int u2=u;
    int tr=3;
    for(int i=1;i<n;i++){
      int v=u2/tr;
      v%=3;
      u2=u2-(u2%(tr*3))+(u2%tr)*3+v;
      if(dist[u2]>dist[u]+1){
        dist[u2]=dist[u]+1;
        que.push(u2);
      }
      tr*=3;
    }
  }
  for(int i=0;i<q;i++){
    string s;
    cin>>s;
    int a=0;
    int t=1;
    for(int j=0;j<n;j++){
      a+=((int)s[j]-65)*t;
      t*=3;
    }
    cout<<dist[a]<<endl;
  }
  return 0;
}