Official
C - One More aab aba baa Editorial by physics0523
この解説では、以下の \(2\) つの解法を取り扱います。
- 探索による解法
- next_permutation を利用する解法
1. 探索による解法
各文字を並べ替えて作ることが可能な文字列を列挙することを考えます。
基本的な方針として、文字の並べ替えを \((1,2,\dots,|S|)\) の順列を列挙していくのに似た方針で行うことが出来ます。
この方針で進めるならば、再帰による実装が楽でしょう。 \(S\) 中のまだ使われていない文字から \(1\) 文字選び、それを探索中の文字列の末尾に挿入することを再帰的に行えばよいです。文字の使用不使用の状況を管理するのは、整数の bit 表現を利用するとよいです。
文字列の列挙が終われば、最後にソートして重複を削除すれば答えを求めることが出来ます。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int l;
string s,t;
vector<string> res;
void find(int fl){
if(fl==0){
res.push_back(t);
return;
}
for(int i=0;i<l;i++){
if(fl&(1<<i)){
t.push_back(s[i]);
find(fl^(1<<i));
t.pop_back();
}
}
}
int main(){
int k;
cin >> s >> k;
l=s.size();
find((1<<l)-1);
sort(res.begin(),res.end());
unique(res.begin(),res.end());
cout << res[k-1] << '\n';
return 0;
}
2. next_permutation を利用する解法
実は、何らかの順列を与えると、辞書順で次の順列を求める next_permutation というアルゴリズムが存在します。
今回は next_permutation の内部の解説は省略しますが、このアルゴリズムは要素に重複があっても動作し、さらに C++ では標準ライブラリ内に実装されています。
これを利用することにより、非常に簡潔な記述で順列の列挙が可能となります。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
int k;
cin >> s >> k;
sort(s.begin(),s.end());
while(k>1){
next_permutation(s.begin(),s.end());
k--;
}
cout << s << '\n';
return 0;
}
posted:
last update: