JOI 2020/2021 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#B - パンケーキ (Pancake)
僕が作成、提出したコードは、以下のとおりです。
/* 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; }