D - "redocta".swap(i,i+1) Editorial by physics0523
解法1. 探索する
\(S\) から始めて atcoder
にするまでに操作が最小で何度必要かどうかを、現在の文字列を頂点とみなして幅優先探索の要領で探索することができます。
実装の過程で、 queue(キュー) や map(連想配列) などを利用すると便利です。
計算量は文字列の長さを \(|S|\) として \(O(|S|!)\) です (が、今回は \(|S|=7\) で固定であるため計算量は定数時間となります。)
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
map<string,int> mp;
queue<string> q;
mp[s]=0;
q.push(s);
while(!q.empty()){
string current=q.front();q.pop();
if(current=="atcoder"){
cout << mp[current] << "\n";
return 0;
}
for(int i=1;i<7;i++){
string next=current;
swap(next[i-1],next[i]);
if(mp.find(next)==mp.end()){
q.push(next);
mp[next]=mp[current]+1;
}
}
}
return 0;
}
解法2. 「転倒数」を利用する
atcoder
は \(7\) 文字全てが異なることに注意すると、 atcoder
の \(i\) 文字目を整数 \(i\) に置き換える操作を考えることができます。
例えば、 catredo
という入力を \((3,1,2,7,6,5,4)\) という数列に置き換えることができます。
この数列を \((1,2,3,4,5,6,7)\) に並べ替えるために必要な隣接要素の交換の最小回数は、「転倒数」という名前の付いた有名問題です。
具体的な解法はここでは省略しますが、例えば Chokudai Speedrun 001-J がこの「転倒数」を求める問題そのものです。
計算量は \(O(|S| \log |S|)\) です (が、先ほど同様 \(|S|=7\) で固定なのでこちらも定数時間です。)
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
vector<int> bit;
int sum(int i){
int s=0;
while(i>0){
s+=bit[i];
i-=i&(-i);
}
return s;
}
void add(int i,int x){
while(i<bit.size()){
bit[i]+=x;
i+=i&(-i);
}
}
int main(){
bit.resize(10);
for(int i=0;i<10;i++){bit[i]=0;}
string s;
cin >> s;
map<char,int> mp;
string atc="*atcoder";
for(int i=1;i<=7;i++){
mp[atc[i]]=i;
}
vector<int> a={-1};
for(int i=0;i<7;i++){
a.push_back(mp[s[i]]);
}
int res=0;
for(int i=1;i<=7;i++){
res+=(i-1-sum(a[i]));
add(a[i],1);
}
cout << res << "\n";
return 0;
}
posted:
last update: