AtCoder ABC 150 C - Count Order (茶色, 300 点)

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

問題へのリンク

問題概要

の順列 が与えられます。

• が の順列のうち辞書順で何番目か
• が の順列のうち辞書順で何番目か

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

制約

• 

考えたこと

制約が小さいので、 通りの順列をすべて列挙することができる。それらを辞書順に に番号付けして、 の番号の差を答えれば OK。

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

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

• 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;
}