Count Order [AtCoder Beginner Contest 150 C]

https://atcoder.jp/contests/abc150/tasks/abc150_c

解説

https://atcoder.jp/contests/abc150/submissions/9407367

パット見て難しい問題に見えるかもしれない。
この問題は制約から解法を考えていく問題である。

問題の解法を考えるときに、全探索できるかを考えるのは、基本である。
今回のN!通りの8!通りは4*10⁴通りくらいであり、これは全探索可能。
10⁵通りくらいまでは全探索でき、10⁶くらいまでギリいけるときがある感じに思っているといい。

さて、あとはどうやって全探索するかであるが、
C++には順列を辞書順で小さい方から全探索する関数がある。
C++でnext_permutationを使ってやると簡単に実装できる。

int N, P[8], Q[8];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> P[i];
    rep(i, 0, N) cin >> Q[i];
    
    vector<int> v;
    rep(i, 0, N) v.push_back(i + 1);
    int idx = 0, a = -1, b = -1;
    do {
        bool ok = true;
        rep(i, 0, N) if (v[i] != P[i]) ok = false;
        if (ok) a = idx;

        ok = true;
        rep(i, 0, N) if (v[i] != Q[i]) ok = false;
        if (ok) b = idx;

        idx++;
    } while (next_permutation(all(v)));

    int ans = abs(a - b);
    cout << ans << endl;
}