😽

ABC 253 C - Max - Min Queryのメモ

2022/10/11に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。

考察

多重集合という言葉に馴染みがなかったのですが、要するに値の重複がありうる集合のようです。
クエリ2はちょっとわかりづらいですが、 $c$ が $x$ の個数よりも大きければ $x$ は全部消えることになるというだけですね。

$Q$ の最大値が $2\times10^5$ とそれなりに大きいので、各クエリの処理が $O(N)$ とかかかってしまうと間に合わなくなりそうです。
たとえばこの $S$ を可変長配列で持つとすると、追加は初期値を十分に大きくしておけば定数時間でいけるとしても、要素の削除や最小値・最大値の取得は線形時間がかかるので間に合いません。

こういう問題は実際には操作をせずになんとかする方法を考えるか、実際に操作をしても大丈夫なデータ構造を使うかのどちらかになると思います。今回は後者でいけそうな雰囲気を感じたのでまずそちらで考えてみました。要素の削除と、最小値・最大値の取得が定数時間とかでできれば普通に間に合うので。

最小値と最大値については、ソートしておけば定数時間で取れるはずです。もちろん、毎回 $O(N log N)$ とかかかってたら全然ダメですが…
具体的には忘れましたがが、既にほぼソート済なら高速にソートできるアルゴリズムもあったと記憶しているので、それを使えば問題ないでしょう。
とここで、ソート済の状態でデータを保持するクラスとしてJavaにはTreeMapがあるのを思い出しました。内部的にどのようなデータ構造、アルゴリズムを用いているのかは詳しく知らないですが、要素を追加するたびに $O(N log N)$ の時間がかかるような残念な実装にはなっていないでしょう。たぶん。

ざっと調べたところ、内部的に二分探索木なので挿入、削除、検索いずれも $O(log N)$ でいけるようです。

最高ですね。これを使えばできてしまいそうです。

提出コード

普段はKotlinを使っていますが、今回はなんとなくJavaを使ってみました。TreeMapはKotlinからも使えるので実用上はどちらでもいいのですが。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws IOException {
        var br = new BufferedReader(new InputStreamReader(System.in));
        var treeMap = new TreeMap<Integer, Integer>();
        var out = new PrintWriter(System.out);

        var q = readInt(br);

        for(int i = 0; i < q; ++i) {
            var query = readInts(br);
            var type = query[0];

            if(type == 1) {
                var x = query[1];
                if(treeMap.containsKey(x)) {
                    treeMap.put(x, treeMap.get(x) + 1);
                } else {
                    treeMap.put(x, 1);
                }
            } else if(type == 2) {
                var x = query[1];
                var c = query[2];

                var count = treeMap.get(x);
                if(count == null) {
                    continue;
                }

                if(count <= c) {
                    treeMap.remove(x);
                } else {
                    treeMap.put(x, count - c);
                }
            } else if(type == 3) {
                out.println(treeMap.lastKey() - treeMap.firstKey());
            }
        }

        out.flush();
    }

    private static int readInt(BufferedReader br) throws IOException {
        return Integer.parseInt(br.readLine());
    }

    private static int[] readInts(BufferedReader br) throws IOException {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

$x$ をキー、 $x$ の個数をバリューとしたTreeMapを定義して使います。最大値はlastKey()、最大値はfirstKey()を呼ぶだけで取れるので楽ちんです。
クエリ2の時は基本的には個数を減らした値で更新しますが、firstKey()を呼んだ時に0が取れると困るため、個数が0になる場合は要素自体を消します。

入力値の受け取りはScannerを使うと便利かもしれませんが、この問題は入力が大量になる可能性があり、Scannerだと遅そうなのでBufferedReaderを使っています。
出力も大量になるかもしれないので、PrintWriterを使います。

いい感じです。

感想

思ったより簡単でした。次は難しそうな問題に挑戦したいです。
~~意味わからんCEとかWAとか出ていますが見なかったことにしてください~~

考察

提出コード

感想

Discussion