けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 150 C - Count Order (300 点)

next_permutation の練習になりそう。DFS でも。

問題へのリンク

問題概要

 1, 2, \dots, N の順列  p, q が与えられます。

  •  p 1, 2, \dots, N の順列のうち辞書順で何番目か
  •  q 1, 2, \dots, N の順列のうち辞書順で何番目か

を求め、それらの差を答えよ。

制約

  •  1 \le N \le 8

考えたこと

制約が小さいので、 N! 通りの順列をすべて列挙することができる。それらを辞書順に  0, 1, \dots, N!-1 に番号付けして、 p, q の番号の差を答えれば OK。

そして、順列の全列挙は、実は C++ なら next_permutation() を使うことで簡潔に実現できる!

next_permutation() は、要素数  N の順列が与えられたときに、辞書順で「次」の順列を返してくれる。たとえば

  • v = (2, 1, 3, 0) の next_permutation() は、(2, 3, 0, 1)
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;

int N;
vector<int> p, q;

int main() {
    cin >> N;
    vector<int> p(N), q(N);
    for (int i = 0; i < N; ++i) cin >> p[i], --p[i];
    for (int i = 0; i < N; ++i) cin >> q[i], --q[i];

    // 各順列が何番目かを求める
    map<vector<int>, int> ord;
    int iter = 0;

    // スタートとなる順列
    vector<int> v(N);
    for (int i = 0; i < N; ++i) v[i] = i;

    // 順番に
    do {
        ord[v] = iter++;
    } while (next_permutation(v.begin(), v.end()));

    cout << abs(ord[p] - ord[q]) << endl;
}