【分野別 初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【全探索：順列全探索】

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の2-3. 分野別　初中級者が解くべき過去問精選 100 問を初級者がC++で解いていきます。

全探索：順列全探索

15　AtCoder Beginner Contest 145 C - Average Length

町を訪れる順番を順列で表現する。距離は計算するだけ。
判定時の誤差を最小化するためにsetprecision()を使った。
C++って階乗を返す標準関数はないのでしょうか。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

ll factorial(ll n) {
  if (n == 1) return 1;
  ll tmp = factorial(n - 1);
  return n * tmp;
}

int main() {
  ll N;
  cin >> N;
  
  vector<ll>x(N), y(N), g(N);
  rep(i, 0, N) {
    cin >> x.at(i) >> y.at(i);
    g.at(i) = i;
  }
  
  double ans = 0;
  do {
    double tmp2 = 0;
    rep(i, 0, N - 1) {
      double tmp1 = sqrt(pow(x.at(g.at(i)) - x.at(g.at(i + 1)), 2) + pow(y.at(g.at(i)) - y.at(g.at(i + 1)), 2));
      tmp2 += tmp1;
    }
    ans += tmp2;
  }while(next_permutation(all(g)));
  
  ll tmp3 = factorial(N);
  
  cout << fixed << setprecision(10);
  cout << ans / tmp3<< endl;
}

16　AtCoder Beginner Contest 150 C - Count Order

do-whileとnext_permutation()を使ってPとQがそれぞれ辞書順で何番目かを探して、差をとる。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define fore(i, n) for(auto &i:n)
#define all(x) x.begin(), x.end()
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> P(N), Q(N), R(N);
  rep(i, 0, N) cin >> P.at(i);
  rep(i, 0, N) cin >> Q.at(i);
  
  rep(i, 0, N) R.at(i) = P.at(i);
  sort(all(R));
  int n = 1;
  int num_p = 0, num_q = 0;
  do {
    bool is_p = true, is_q = true;
    rep(i, 0, N) {
      if (R.at(i) != P.at(i)) is_p = false;
      if (R.at(i) != Q.at(i)) is_q = false;
    }
    if (is_p) num_p = n;
    if (is_q) num_q = n;
    n++;
  }
  while(next_permutation(all(R)));

  cout << abs(num_p - num_q) << endl;
}

17　ALDS_13_A - 8 クイーン問題

AIZU ONLINE JUDGE に登録していないので、後回し。