AtCoderログ：0092 - ABC 215 C

問題

問題文

文字列 $S$ の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から $K$ 番目にくる文字列を求めてください。

制約

・$1 \le |S| \le 8$
・$S$ は英小文字のみからなる
・$S$ の各文字を並べ替えてできる文字列は $K$ 種類以上存在する

回答

回答1 (AC)

文字列 $S$ の各文字を並べ替えた文字列を調べていくことになるので、next_permutation 関数を利用するのが簡単です。受け取った文字列 s を小さい順にソートしてから next_permutation 関数を k 回適用することで、所望の文字列を求めることができます。コードは以下のようになりました。

abc215c-1.cpp

#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 -= 1;
  }

  cout << s << endl;
}

調べたこと

AtCoder の解説 → 公式解説

$S$ の文字列を入れ替えてできる文字列を列挙する方法と、回答1と同じように next_permutation を使う方法が紹介されていました。

AtCoder の解説 → ユーザ解説

next_permutation を使う方法が紹介されていました。

リンク

前後の記事

• 前の記事 → AtCoderログ：0091 - ABC 215 B