2021年8月20日に開催された AtCoder Beginner Contest 215（ABC215） に参加しました。

AtCoder Beginner Contest 215 – AtCoder

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

結果は
・結果: 4完（A,B,C,D） 0WA
・順位: 1857 / 8537
・パフォーマンス: 1162
・レーティング: 652 → 715
でした。

C問題について

問題等は以下のリンクよりご確認ください。

C – One More aab aba baa

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

まずは計算量の予測について。

制約が\(1 \leq |S| \leq 8\)です。

順列の組み合わせの数\(_nP_r\)は、\(_8P_8 = \frac{8!}{(8-8)!} = \frac{8!}{1} = 40,320 \)となります。

すなわち、\(40,320\)通りは全列挙できる個数なので、全列挙する方法で進めます。

C++の場合、do-whileとnext_permutationを使えば順列を全列挙することができます。

ACできたのはいいものの…

今回はコンテストでは以下のコードを提出しACしました。

しかし、このコードはまどろっこしいというか、余計な処理をしています。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<int, int>;
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;

int main() {
  string S;
  int K;
  cin >> S >> K;

  set<string> k;

  vector<int> v;

  for (int i = 0; i < int(S.size()); i++) {
    v.push_back(i);
  }

  do {
    string s = "";
    for (int i = 0; i < int(S.size()); i++) {
      s += S[v[i]];
    }
    k.insert(s);
    // cout << s << endl;
  } while (next_permutation(v.begin(), v.end()));

  vector<string> ans;
  for (auto i : k) {
    ans.push_back(i);
  }

  cout << ans[K - 1] << endl;
  return 0;
}

全体の処理を見ていきます。

\(0\)から\(S\)の文字数\(- 1\)までが入る配列\(v\)を作って、この配列\(v\)の順列を作っています。

\(S\)が\(3\)文字の場合は、以下のような順列を列挙しています。

0 1 2 
0 2 1 
1 0 2 
1 2 0 
2 0 1 
2 1 0 

上の順列で出た値は何文字目の文字を使うかを指定する数と考えることができます。

例えば 1 0 2 の場合は、\(1\)文字目\(+ 0\)文字目\(+ 2\)文字目となります。

そこでできた文字列をset\(k\)に追加していきます。

順列の列挙が終わったら、set\(k\)の\(K-1\)番目を取り出して出力する、という流れになっています。

next_permutationは文字列にも使える

上のコードのよくないことはnext_permutationは数値の配列しか使えないと思っていたことです。

next_permutationは文字列でも使えます。

しかし、並び替えをしておかないといけないという点に気をつけなければなりません。

反省後、ACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using P = pair<ll, ll>;
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;

int main() {
  string S;
  int K;
  cin >> S >> K;

  vector<string> ans;
  sort(S.begin(), S.end());

  do {
    ans.push_back(S);
  } while (next_permutation(S.begin(), S.end()));

  cout << ans[K - 1] << endl;
  return 0;
}