[ABC314] G - Amulets

[Q] https://atcoder.jp/contests/abc314/tasks/abc314_g

レート溶けちゃった。
E,Fが苦手な期待値だったので、Gを頑張っていました。

考察
1. 入力順に処理していこうと思う。i = 0,1,…,(N-1)について、iを固定して考える。
2. type別の攻撃の総和を2つのmultisetで管理すればうまくいく。
受ける攻撃のattackedと、お守りで防ぐguardで管理。
3. 初期状態は、全部attackedに0の攻撃をM種類のタイプで受けるとする。
4. multisetの状態を入力値に従って更新。
5. attackedの最大値 <= guardの最小値
になるように整理する。
6. 攻撃を受けられなくなるまでattackedに移していく。
7. ans[お守りの数] = 討伐できるモンスター数でメモしていく。

実装

int main() {
  cincout();
  ll N, M, H;
  cin >> N >> M >> H;
  vector<ll> ans(M + 1);
  multiset<ll> attacked, guard;  // 受ける攻撃、お守りで防ぐ攻撃
  vector<ll> damage(M, 0);
  ll h = H;  // 今の残りHP
  rep(i, M) attacked.insert(0);
  rep(i, N) {
    ll a, b;
    cin >> a >> b;
    --b;
    // まずお守りで防いでいるか確認
    if (guard.count(damage[b])) {
      guard.erase(guard.find(damage[b]));
      damage[b] += a;
      guard.insert(damage[b]);
    } else {
      // 攻撃に含まれている
      attacked.erase(attacked.find(damage[b]));
      h += damage[b];
      damage[b] += a;
      // いったん、attackedに戻す。
      // attackedの末尾 <= guardの先頭になるようにする。
      attacked.insert(damage[b]);
      h -= damage[b];
 
      // attackedの最大値をお守りに移す。
      ll ar = *attacked.rbegin();
      h += ar;
      guard.insert(ar);
      attacked.erase(attacked.find(ar));
      // お守りを外していく
      ll gb = *guard.begin();
      while (!guard.empty() && (h - gb) > 0) {
        h -= gb;
        attacked.insert(gb);
        guard.erase(guard.begin());
        gb = *guard.begin();
      }
    }
    // 更新
    ans[guard.size()] = i + 1;
  }
  for (ll i = guard.size(); i <= M; ++i) {
    ans[i] = N;
  }
  rep(i, M + 1) { cout << ans[i] << " \n"[i == M]; }
}

https://atcoder.jp/contests/abc314/submissions/44572086

Q. 本番でなぜ間に合わなかったの？
A. 1つのmultisetで無理やり頑張ってしまった。

攻撃を受けられるborder値 = recieveの末端値をメモしておいたが、
HP7
S = {2, 3, 3, 4}
3が複数あってborder値が3のときに管理できず悩むことになった。
結局multisetを2つ用意すればいいだけだった。

Q. なぜずっとコンテスト後もWAしてたの？
A. 解答の更新を、attackedのときだけしか走らせていなかったよ。
意識的にelse外に書いたはずだった。どこかのタイミングで中に書いてしまったんだろう。

    else{
      // 更新
      ans[guard.size()] = i + 1;
    }