AtCoderログ：0122 - ABC 150 C

問題

問題文

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

制約

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

収録されている問題セット

• AtCoder Problems Boot camp for beginners Easy 100 [#025]

回答

回答1 (AC)

順列の順序に関する問題なので、next_permutation() 関数を使用するのが簡単です。数列 $P,Q$ を順列として読み込んだ後、最も小さい順列 $(1,2,\dots,N)$ を初めとして next_permutation() によって小さい順に順列を生成し、$P,Q$ に等しいときはそのカウンタ値を記憶します。そして最後に2種類の記憶値の差を求めれば良いです。コードは以下のようになりました。

abc150c-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
 
  vector<int> p(n);
  for ( int i=0; i<n; i++ ) {
    cin >> p.at(i);
  }

  vector<int> q(n);
  for ( int i=0; i<n; i++ ) {
    cin >> q.at(i);
  }
  
  vector<int> r;
  for ( int i=1; i<=n; i++ ) {
    r.push_back(i);
  }
  
  int a, b, counter = 1;
  do {
    if ( p==r ) {
      a = counter;
    }
    if ( q==r ) {
      b = counter;
    }
    counter += 1;
  } while ( next_permutation(r.begin(),r.end()) );
  
  cout << abs(a-b) << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0121 - ABC 092 B