振り返り Atcoder ABC150 C問題

目的

公式解説を観てもよく分からなかった人向けに個人的な備忘もかねた解説メモ

対象の問題

ABC150 C - Count Order

解法の大まかな流れ

1. 順列を辞書順で全て作成する
   • mpというMapを作成
   • key:順列
     • 例えば1~3ならば、 {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}の順でkeyとして格納される
   • value:keyで作成された順列の辞書順の番号。0はじまり
     • keyが{1,2,3}なら0。keyが{3,2,1}なら5
   • 辞書順の順列生成はnext_permutationという関数を使う
2. mpに順番を求めたい2つの順列を与えて、差分の絶対値をとる

解説のコードにコメント追記

こちらの解説コードにコメントを追記

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  rep(i,n) cin >> p[i];
  rep(i,n) cin >> q[i];
  vector<int> a(n);
  rep(i,n) a[i] = i+1;

  map<vector<int>, int> mp;
  do {
    mp[a] = mp.size();
    //辞書順に順列を生成してmpに格納するので、mapのキーペアの数(サイズ)をとれば
    //それが順番になる。それを生成した順列に対応するkeyとして格納
  } while (next_permutation(a.begin(), a.end()));

  int ans = abs(mp[p] - mp[q]);
  //cf) mp[p]つまりmp[{1,3,2]のkeyは1。mp[q]つまりmp[(3,1,2}]のkeyは4
  // ansで差分の絶対をとるので、上記例だと3

  cout << ans << endl;
  return 0;
}