AtCoderのABC-Cがわからないです。

Question

https://atcoder.jp/contests/abc150/tasks/abc150c
こちらの問題の解説放送で解説していたコードが以下のものになりますがコードを理解できていないので質問させていただきます。

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

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();//1
  }
  while (next_permutation(a.begin(),a.end()));
  
  int ans = abs(mp[p]-mp[q]);
  cout << ans << endl;
  return 0; 
}

1.mapではオブジェクト名[キー]=値と書くと思うのですが今回キーと値はどのような対になっているのでしょうか?よろしくお願い致します。

Comments

[episteme]

AtCoderの件の問題が見当たらん。リンクの貼り損ね?

[cunwe]

すいません、こちらからお願い致します。
https://atcoder.jp/contests/abc150/tasks/abc150_c

Answer 1

vector<int> a(n);
rep(i,n) a[i]=i+1; // a = [0, 1, 2 ... n-1]

map<vector<int>, int> mp;
do {
  mp[a]=mp.size();//1
} while (next_permutation(a.begin(),a.end()));

next_permutation()で順列を発生させ、そいつをmapに突っ込んでるから、
mp の key -> value は:

[0, 1, 2] -> 0
[0, 2, 1] -> 1
...
[2, 1, 0] -> 5

...問題を忠実に実装してますね。

Comments

[cunwe]

理解できました、今回も教えていただきありがとうございます！

[cunwe]

そこまではepistemeさんのお陰でわかりましたがすいません、もうひとつ質問がございます。リファレンスによるとオブジェクト名.size()でコンテナ内の要素の数を返すそうなのですがそれがepistemeさんがおっしゃった0,1,5などがそれに当たるということだと思うのですが今回で言うとコンテナというのはなんでしょうか？

[episteme]

コンテナはその名のとおり"入れ物"です。
ここでは map<vector<int>,int> が
「vector<int> と int の組」を
複数個格納するコンテナです。
メンバ関数 size() は コンテナ内の要素数を返します。

[cunwe]

すいません、混乱してしまいました。mp.size()はコンテナ内の要素の数を返す関数でありながら値でもあるということでしょうか？

[episteme]

そんなこといってません。
「関数 abs(x) はxの絶対値を返します」って言いまわし、わかんない?

[cunwe]

今回で言うとmp[a]=mp.size();においてはmpに引数を渡すとmp,sizeという関数が値を返すということでしょうか？

[episteme]

「a と mp.size() の組」を mp に追加しています。

[cunwe]

理解できました、ありがとうございました。

[episteme]

...ホントに理解できてるかな?
mp[a] = mp.size() がどんなカラクリで「a と mp.size() の組を mp に追加」してるか説明できる?

[cunwe]

epistemeさんの例を引用させていただきますと、[0,1,2]をkey、0をvalueとして(0-indexedだから)、mp.size()がmpコンテナの要素数である、現時点では1を返すという仕組みではないですか？間違っていましたらぜひ修正していただきたいです。

[episteme]

mp[a] は mpがkey:aを持っていれば対となるvalueの参照を返す。
もっていなければ対となるvalueを作り、その参照を返す。
このコードでは後者。valueの参照に対し = mp.size() してるから、mp.size()でvalueを書き換えてる。

[cunwe]

すいません、やはり理解できてないようです。リファレンスによるとkeyを指定してvalueを高速に取り出せるクラスというのがmapらしいのですがkeyがないということはありえるのですか？(そもそもkeyがないとvalueを取り出せないのではないですか？)このコードではkeyを持っていないということですがnext_permutationで[0,1,2]などの順列(ここでのkey)を生成させているのではないですか？度重なる質問で恐縮ですがご回答よろしくお願い致します。

[episteme]

1. 空のmap<vector<int>,int> mp を用意
2. vector<int> a = { 0, 1, 2 }
3. mp[a] でmpからaを探す。ないので ([0,1,2], 0) を追加して0への参照を返す
4. 0への参照を mp.size() に置き換えるので mp内は {[0,1,2], 1)　となる。
5. next_permutation() により a = [0, 2, 1]。3)に戻る... の繰り返し。
※ 4) において右辺が先に評価されれば mp.size() == 0 だが、最終的に差を取るのでコタエは同じ。

[cunwe]

順番に丁寧に説明してくださり、ありがとうございます。ようやく理解できました。