【AtCoder】ABC 448 C - Except and Min

C - Except and Min

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 262 / NoviSteps: 2Q / 配点: 300 点

問題概要

$1$ から $N$ の番号がついた $N$ 個のボールが袋に入っており、ボール $i$ には整数 $A_i$ が書かれている。

$Q$ 個のクエリを処理せよ。

各クエリでは長さ $K$ の数列 $(B_1, B_2, \dots, B_{K})$ が与えられるので以下の操作を行え。 ここで、$B_i$ は全て $1$ 以上 $N$ 以下で、かつ相異なる。

• まず、ボール $B_1, B_2, \dots, B_K$ を全て袋から取り出す。
• そして、現在の袋に入っているボールに書かれた整数の最小値を出力する(この時、袋は空でないことが制約から保証されている)。
• その後、取り出した $K$ 個のボールを全て袋に戻す。

制約

• $6 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq K \leq 5$
• $1 \leq B_1 \lt B_2 \lt \dots \lt B_K \leq N$
• 全てのクエリに対する $K$ の総和は $4 \times 10^5$ 以下
• 入力される値は全て整数

考察

ボールの出し入れをしながら、要素の最小値を求めなければならない。

これは、袋の中に入ったボールに書かれている整数をmultisetで管理することで効率的に実現できる。

具体的には、以下のようになる。

• $K$ 個のボールを全て袋から取り出す: multiset.erase()
• 現在の袋に入っているボールに書かれた整数の最小値を出力する: *multiset.begin()を出力
• 取り出した $K$ 個のボールを全て袋に戻す: multiset.insert()

なお、eraseの引数に $A_{B_i}$ のポインタを渡してあげることで、同じ値が複数あっても1つずつ消すことができる。 値を直接渡すと、同じ値が複数あったときに全て消えてしまう可能性があるため注意すること。

計算量は、multisetの挿入・削除操作が $O(\log N)$ であるため、全体で $O((N + \sum K) \log N)$ となる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, Q;
11.    cin >> N >> Q;
12.    vector<int> A(N);
13.    multiset<int> st;
14.    rep(i, 0, N) cin >> A[i], st.insert(A[i]);
15. 
16.    while (Q--)
17.    {
18.        int K;
19.        cin >> K;
20.        vector<int> B(K);
21.        rep(i, 0, K) cin >> B[i], B[i]--;
22. 
23.        rep(i, 0, K)
24.        {
25.            if (st.contains(A[B[i]]))
26.                st.erase(st.find(A[B[i]]));
27.        }
28. 
29.        cout << *st.begin() << endl;
30. 
31.        rep(i, 0, K) st.insert(A[B[i]]);
32.    }
33. 
34.    return 0;
35.}

Submission #73900173 - AtCoder Beginner Contest 448

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実装時間: 10 分

コメント

なんか公式解説にmultiset解法がなくてびっくり。