こんにちは。昨日はABC170でした。
Eが、multisetとかいうのを使って実装すれば解けるよって解説に書いてあったのでやってみたところ、1つだけWAが出てわけわからんになったので（https://atcoder.jp/contests/abc170/submissions/14384348）ここで整理しながら丁寧に解いてみよう、という記事です。
（！！！まだACできてません何がおかしいんだ！？！？！？）
↑ってなってましたが解決しました！
問題
用意するもの
公式解説pdf（https://img.atcoder.jp/abc170/editorial.pdf）を参考に。以下のものを用意します。今回は、園児の番号を1-indexで（入力そのままに）扱うのでサイズN+1の配列がでてくる。
- 各園児のレートを表す配列
vector<int> rate(N+1);。これは最初に入力したら以後書き換えはしない - 各園児が所属する幼稚園の番号を示す
vector<int> belong(N+1);。これは適宜書き換えていく。 - 各幼稚園に幼稚園に所属する幼児のレートの順序付き多重集合（の配列）
vector<multiset<int>> youchien(200010);。配列のサイズとしては $2\times 10^{5}$ よりちょっと多めにしておく（一応）。 - 各幼稚園の最強園児のレートの順序付き多重集合
multiset<int> maxenji;。
使い方確認
それぞれの使い方を確認する。
vector rate(N+1)
rate[i] = 幼児iのレート
vector belong(N+1)
belong[i] = 幼児iが所属している園の番号
vector<multiset> youchien(200010)
multisetの中身は小→大と並ぶことに注意する
youchien[i] = 幼稚園iにいる幼児のレート一覧
入力例1の初期状態では
youchien[1] = {1, 8}
youchien[2] = {2, 6}
youchien[3] = {1, 9}
*youchien[i].rbegin() = 幼稚園iの最強園児のレート
入力例1の初期状態では *youchien[1].rbegin() = 8
multiset maxenji
maxenji.begin() = 「平等さ」
各クエリに対する処理
解説pdfからちょっと変更。カッコの中の数字は、解説pdfの順番
転園する幼児は $c$ 、転園する前の園の番号を $F$ 、転園する先の園の番号を $T$ とする。
クエリの入力 $C,D$からは、
c = C F = belong[C] T = D
という対応になっている。
まずは、転園に関わる園の最強園児レートをmaxenjiから削除する
maxenjiから、現在の$F$の最強園児のレートを削除する（1）
maxenji.erase(*youchien[F].rbegin());
問題あり！後で修正
- （現在の$T$に幼児がいるなら）
maxenjiから、現在の$T$の最強園児のレートを削除する（3）
if(!youchien[T].empty()){
maxenji.erase(*youchien[T].rbegin());
}
問題あり！後で修正
転園処理
- 幼稚園$F$から$C$のレートを削除する（5）
youchien[F].erase(rate[c]);
問題あり！後で修正
- 幼稚園$T$に$C$のレートを挿入する（6）
youchien[T].insert(rate[c]);
maxenjiにFとTの新しい最強園児レートを入れる
maxenjiに、$F$の新しい最強園児のレートを、挿入する（転園によって$F$に園児が一人もいなくなった場合何もしない）（2）
if(!youchien[F].empty()){
maxenji.insert(*youchien[F].rbegin());
}
maxenjiに、$T$の新しい最強園児のレートを、挿入する（4）
maxenji.insert(*youchien[T].rbegin());
転園した幼児の所属園番号を書き換えてあげる
（7）
belong[c] = T;
「平等さ」の出力
cout<<*maxenji.begin()<<endl;
入力
for(int i=1; i<=N; i++){ int a,b;cin>>a>>b; rate[i] = a; belong[i] = b; youchien[b].insert(a); } for(auto x: youchien){ if(x.empty())continue; maxenji.insert(*x.rbegin()); }
提出(WA)
WA→https://atcoder.jp/contests/abc170/submissions/14386806
テストケースhandmade09でWAが出る。クエリの何個めでおかしくなってるのか、テストケースを入手して（https://www.dropbox.com/sh/nx3tnilzqz7df8a/AACKrnT4pbaq3T6uTf5hTrAka/ABC170/E?dl=0&subfolder_nav_tracking=1から）調べたら
NOT equal at 13530 O:24951766, X:24990239 NOT equal at 39817 O:67095552, X:67123496
ということだったのだが…………
解決
問題あり！と書いていたところの何が問題だったのかが判明しました。
multiset msに要素iが複数入っているとき、ms.erase(i)を実行すると全ての要素iが消去される
というところに引っかかっていました。つまり
maxenji = {2, 2, 4, 5}
のとき
maxenji.erase(2)
をしたあと
maxenji = {2, 4, 5}
を期待していたが実際は
maxenji = {4, 5}
となる
解決策1
複数個削除してしまったら戻してあげる。eraseに探すキーを入れると「削除した数」が返ってくるのでそれを利用する
int e = maxenji.erase(*youchien[F].rbegin()); if(e>1) maxenji.insert(*youchien[F].rbegin()); if(!youchien[T].empty()){ e = maxenji.erase(*youchien[T].rbegin()); if(e>1) maxenji.insert(*youchien[T].rbegin()); } e = youchien[F].erase(rate[c]); if(e>1) youchien[F].insert(rate[c]);
AC→https://atcoder.jp/contests/abc170/submissions/14388918
解決策2
eraseの引数として要素iのイテレータを（findしてから）入れる
auto itr = maxenji.find(*youchien[F].rbegin()); if(itr!=maxenji.end()){ //今回は「発見できない」はない maxenji.erase(itr); } //短縮↓ maxenji.erase(maxenji.find(*youchien[F].rbegin()));
maxenji.erase( maxenji.find(*youchien[F].rbegin()) );
if(!youchien[T].empty()){
maxenji.erase( maxenji.find(*youchien[T].rbegin()) );
}
youchien[F].erase( youchien[F].find(rate[c]) );
AC→https://atcoder.jp/contests/abc170/submissions/14389712
まとめ
multisetは初めて触った。最終的に解説pdfに沿って実装ができたのでよかった。おしまい。
