【AtCoder】ABC 466 D - Placing Rooks

D - Placing Rooks

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

AtCoder

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

問題概要

$N \times N$ のマス目があり、最初、マス目の上には何も置かれていない。

高橋君がマス目に対して $M$ 回の操作を順に行う。 $i$ 回目の操作は以下のとおりである。

• 上から $R_i$ 行目のマスに置かれているコマをすべて取り除く。
• 次に、左から $C_i$ 列目のマスに置かれているコマをすべて取り除く。
• 最後に、上から $R_i$ 行目かつ左から $C_i$ 列目のマスにコマを置く。

$M$ 回の操作の後でマス目に置かれているコマの個数を出力せよ。

制約

• $1 \leq N \leq 3\times 10^5$
• $1 \leq M \leq 3\times 10^5$
• $1 \leq R_i \leq N$
• $1 \leq C_i \leq N$
• 入力はすべて整数

考察

$i$ 回目の操作で駒がマス $(R_i, C_i)$ に置かれたとする。

以降の $j$ 回目の操作 $(j > i)$ で、$R_j = R_i$ または $C_j = C_i$ である場合、マス $(R_i, C_i)$ の駒は取り除かれてしまう。

したがって、最終的にマス $(R_i, C_i)$ に駒が残るためには、

• 行 $R_i$ に対して最後に行われた操作が $i$ 回目の操作であること
• 列 $C_i$ に対して最後に行われた操作が $i$ 回目の操作であること

の両方を満たす必要がある。

この条件を満たす $i$ の個数を数えればよい。

実装例

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, M;
11.    cin >> N >> M;
12.    vector<int> R(M), C(M);
13.    vector<int> time_row(N, -1), time_col(N, -1);
14.    rep(i, 0, M) {
15.        cin >> R[i] >> C[i];
16.        R[i]--;
17.        C[i]--;
18. 
19.        time_row[R[i]] = i;
20.        time_col[C[i]] = i;
21.    }
22. 
23.    int ans = 0;
24.    rep(i, 0, M) {
25.        if (time_row[R[i]] == i && time_col[C[i]] == i)
26.            ans++;
27.    }
28. 
29.    cout << ans << endl;
30. 
31.    return 0;
32.}

https://atcoder.jp/contests/abc466/submissions/77373114

atcoder.jp

実装時間: 15分

コメント

この程度なら、行・列ごとにコマの位置を記録した一次元配列を管理して、シミュレーションしてもよさそう。