next_permutationを用いてABC150 C問題を解く

競技プログラミングの備忘録用
C++のnext_permutationを用いて順列を列挙してABC150 C問題を解く．

C - Count Order

問題

大きさ$N$の順列 (($1,2, ..., N$)を並び替えてできる数列) $P,Q$があります。大きさ$N$の順列は$N!$通り考えられます。このうち，$P$が辞書順で$a$番目に小さく、$Q$が辞書順で$b$番目に小さいとして、$|a−b|$を求めてください。

制約

• $2≤N≤8$
• $P, Q$は大きさ$N$の順列である。
• 入力は全て整数である。

方針

$P,Q$のそれぞれについて順列を辞書順に全て列挙し，入力した数列がそれぞれの順列内で辞書順に何番目であるかを求める．順列を列挙する際にはnext_permutationを用いる．昇順ソートした配列をnext_permutationに渡すことで辞書順に順列を列挙してくれる．

next_permutationの使い方

例えばPという数列の順列を全て列挙したいとする．
ここでPはvector型と仮定

sort(P.begin(),P.end());
do{
    for(int i=0; i<P.size(); i++){
        cout << P[i] << " ";
    }
    cout << endl;
}while(next_permutation(P.begin(),P.end()));

まず初めにsortを用いてPを昇順ソートしている．
続いて，do-while文を用いて全ての順列を列挙している．next_permutationは全ての順列を列挙し終えたら-1を返却するため，do-while文から抜けることができる．

今回は以上の方法で順列を列挙し，$P,Q$それぞれの順番を$a,b$に保存しておき最後に$a-b$の絶対値を出力すればよい．

解法コード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector<double> VL;
typedef vector<string> VS;
typedef vector<PLL> VP;
typedef vector<ll> VLL;
const static int INF = 1000000000;
const static int MOD = 1000000007;
#define rep(i,n) for (ll i=0; i<(ll)(n); i++)
#define repd(i,n) for (ll i=n-1; i>=0; i--)
#define rept(i,m,n) for(ll i=m; i<n; i++)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define PF push_front
#define PB push_back
#define SORT(V) sort((V).begin(), (V).end())
#define RVERSE(V) reverse((V).begin(), (V).end())
#define paired make_pair
#define PRINT(V) for(auto v : (V)) cout << v << " "

int main()
{
    int N;
    cin >> N;
    VI P(N),Q(N);
    VI PS(N), QS(N);
    rep(i,N){
        cin >> P[i];
        PS[i]=P[i];
    } 
    rep(i,N){
        cin >> Q[i];
        QS[i]=Q[i];
    }
    sort(all(P));
    sort(all(Q));
    ll a=1; 
    ll b=1;
    bool judge=true;
    do {
        rep(i,N){
            if(P[i]!=PS[i]){
                judge=false;
            }
        }
        if(judge){
            break;
        }
        else{
            a++;
            judge=true;
        }
    }while(next_permutation(all(P)));
    do{
        rep(i,N){
            if(Q[i]!=QS[i]){
                judge=false;
            }
        }
        if(judge){
            break;
        }
        else{
            b++;
            judge=true;
        }
    }while(next_permutation(all(Q)));
    cout << abs(a-b) << endl; 
}