【AtCoder】ABC 406 D - Garbage Removal | 緑コーダーが解くAtCoder

atcoder.jp

配点: 400 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: ??? / NoviSteps: 2Q

問題概要
制約
考察
実装例
コメント

問題概要

$H \times W$ マス目があり、上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表す。

マス目の上には $N$ 個のゴミが落ちており、 $i$ 番目のゴミはマス $(X_i, Y_i)$ に落ちている。 $Q$ 個のクエリが与えられるので、順に処理せよ。各クエリは以下の2形式のいずれかである。

1 x : マス目の $x$ 行目に落ちているゴミの個数を出力する。その後、 $x$ 行目に落ちているゴミはすべて捨てられ、マス目上から取り除かれる。
2 y : マス目の $y$ 列目に落ちているゴミの個数を出力する。その後、 $y$ 列目に落ちているゴミはすべて捨てられ、マス目上から取り除かれる。

制約

$1 \leq H, W, N \leq 2 \times 10^5$
ゴミの位置は相異なる
$1 \leq Q \leq 2 \times 10^5$
入力される値はすべて整数

考察

クエリは行および列を指定するものなので、各行・列ごとに存在するゴミの個数を管理できるようにする。これは、vectorの2次元配列で実現できる。

要素としては、当該行・列に存在するゴミの番号とする。別途長さ $N$ のフラグ配列を用意することで、各ゴミが捨てられたかどうかを判定できるようにするためだ。setを使えばinsert / deleteで実現できるが、今回はvectorなのでそれはできない。

ここまでの内容を基にすると、以下のようなアルゴリズムが考えられる。

各行・列ごとに存在するゴミの個数を管理する二次元配列rows, colsに、それぞれゴミの番号を格納する。
各ゴミが捨てられたかどうかを管理する配列is_removedを用意し、falseで初期化する。
各クエリについて、以下を行う(列についても同様)。
1. 指定された行の各要素について、 is_removed[x]がfalseであるならば、
  1. 答えのカウンターを $1$ 増やす。
  2. is_removed[x]をtrueとする。
2. カウンターを出力する。

しかし、このアルゴリズムでは計算量が $O(NQ)$ となり、 TLE してしまう。

実は、一度操作が行われた行・列はゴミが存在しなくなるので、上述のアルゴリズムの手順 3-1. は高々1回行えばよいことになる。

したがって、新たに操作が行われたかどうかを管理するフラグ配列を用意し、手順 3-1. でその真偽を判定すればよい。詳しくは実装例参照。

これによって、クエリ処理部分の計算量は $O(N + Q)$ となり改善することができた。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int H, W, N;
    cin >> H >> W >> N;
    vector<vector<int>> rows(H), cols(W);
    rep(i, 0, N)
    {
        int X, Y;
        cin >> X >> Y;
        X--, Y--;
        rows[X].push_back(i);
        cols[Y].push_back(i);
    }

    int Q;
    cin >> Q;
    vector<bool> is_removed(N, false);
    vector<bool> is_removed_rows(H, false), is_removed_cols(W, false);
    while (Q--)
    {
        int t;
        cin >> t;

        int cnt = 0;
        if (t == 1)
        {
            int x;
            cin >> x;
            x--;

            if (!is_removed_rows[x])
            {
                for (auto &&i : rows[x])
                {
                    if (!is_removed[i])
                    {
                        cnt++;
                        is_removed[i] = true;
                    }
                }

                is_removed_rows[x] = true;
            }

            cout << cnt << endl;
        }
        else
        {
            int y;
            cin >> y;
            y--;

            if (!is_removed_cols[y])
            {
                for (auto &&i : cols[y])
                {
                    if (!is_removed[i])
                    {
                        cnt++;
                        is_removed[i] = true;
                    }
                }

                is_removed_cols[y] = true;
            }

            cout << cnt << endl;
        }
    }

    return 0;
}