【AtCoder】multiset を使い方

はじめに

筆者はsetを使って問題を解いていると、「setでは解けないぞ」となってmultisetに行きつきました。「これ使う時ありそうだな！」と思って、「multisetで解けそう」と思ったら、multisetでは中々解けなくてmapで解けたことがありました。そこで、それらの例題を通してmultisetの使い方を自分なりに考えたので記事に書こうと思いました。

multisetが使える場面

• 重複度を考慮しての何番目かに大きい/小さい要素を取得する場合にmultisetが使える。配列を違ってソートする必要がないので、計算量的に優れている
• 要素の存在有無だけでなく、重複度も考慮したい場合にmultisetが使えるが、その場合にmapでバリューに重複度を持たせれば、multisetで書けることはmapで書けることも多い

ABC241D - Sequence Query

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

int main() {
  int Q; cin >> Q;
  multiset<ll> ms;
  rep(qi, Q) {
    int t; ll x;
    cin >> t >> x;
    if (t == 1) ms.insert(x);
    if (t == 2) {
      int k; cin >> k;
      auto it = ms.upper_bound(x);
      bool ok = true;
      rep(i, k) {
        if (it == ms.begin()) { ok = false; break; }
        it--;
      }
      if (ok) cout << *it << endl;
      else cout << -1 << endl;
    }
    if (t == 3) {
      int k; cin >> k;
      auto it = ms.lower_bound(x);
      bool ok = true;
      rep(i, k) {
        if (i != 0) it++;
        if (it == ms.end()) { ok = false; break; }
      }
      if (ok) cout << *it << endl;
      else cout << -1 << endl;
    }
  }
}

multisetが使えない場面

• multisetは要素の種類数は求めることができないが、重複を考慮した要素数をO(1)で取得できる
• mapはバリューに要素(キー)の重複度を保持することで、処理過程で要素の重複度を考慮できる上に要素の種類数をO(1)で取得できる。ただし、重複を考慮した要素数取得の計算量はO(N)である

例題：典型90問034 - There are few types of elements（★4）

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

int main() {
  int N, K; cin >> N >> K;
  vi A(N); rep(i, N) cin >> A[i];
  
  map<int, int> mp;
  int j = 0, ans = 0;
  rep(i, N) {
    mp[A[i]]++;
    while (mp.size() > K) {
      mp[A[j]]--;
      if (mp[A[j]] == 0) mp.erase(A[j]);
      j++;
    }
    ans = max(ans, i-j+1);
  }
  
  cout << ans << endl;
}

おわりに

自分がAtCoderの問題を解いてきた中で、multisetを使って解くような問題はほとんど見かけていないのですが、色々なデータ構造を知ることで問題を解く際に考えられる幅も広くなると思います。

もし間違っている箇所や補足したいことなどがありましたら、コメントをいただけますと幸いです。