zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC150-C「Count Order」です。
ポイント
辞書順の順列を考える問題です。c++ではnext_permutationを利用すれば，$N$が大きくないときに，比較的簡単に辞書順の順列を考えることができます。next_permutationについては，以下の記事を参考にしていただければと思います。
あわせて読みたい
【競プロ精進ログ】ABC145-C
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミ...
さらに，今回の問題では，ある数列が辞書順で何番目かを知る必要があるため，mapなどを利用して各配列の辞書順を管理すると便利です。
おさえるべき内容
next_permutation関数の使い方
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
int main(){
int N;
cin >> N;
// mapに突っ込むためvectorで配列を生成する
vector<int> P(N);
vector<int> Q(N);
// next_permutationするための昇順の配列
vector<int> X(N);
rep(i, N) cin >> P[i];
rep(i, N) cin >> Q[i];
rep(i, N) X[i] = i + 1;
// ある配列（1番目の引数）が辞書順で何番目か（2番目の引数）を管理するmap
map<vector<int>, int> D;
// 何番目かの変数
int cnt = 1;
// next_permutationに対応するdo文
do{
// mapに代入
D[X] = cnt;
cnt++;
}
// next_permutationで順列を辞書順で次に進める
while (next_permutation(X.begin(), X.end()));
// 出力
cout << abs(D[P] - D[Q]) << endl;
}
コメント