【AtCoder】ABC 462 C - Not Covered Points

2026-06-14

AtCoder/ABC/C問題 AtCoder/ABC/300点問題 AtCoder/灰Diff AtCoder/NoviSteps/2Q AtCoder/数学/図形/座標幾何 AtCoder/数学/順列競技プログラミング

C - Not Covered Points

C - Not Covered Points

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

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

問題概要

$2$ 次元平面上に $N$ 個の点があり、点 $i$ の座標は $(X_i,Y_i)$ である。ここで、 $X,Y$ はそれぞれ $(1,2,\ldots,N)$ の順列であることが保証される。

左下の頂点を $(0,0)$ 、右上の頂点を $(X_i,Y_i)$ とする $x$ 軸に平行な辺と $y$ 軸に平行な辺のみからなる長方形の内部(辺上を含まない)に、 $N$ 個の点をどれも含まないような $i$ の個数を求めよ。

制約

$1\le N\le 3\times 10^5$
$1\le X_i,Y_i\le N$
$X,Y$ はそれぞれ $(1,2,\ldots,N)$ の順列
入力される値は全て整数

考察

$i \: (1 \leq i \leq N)$ が条件を満たさない条件は、

$X_j < X_i$ かつ $Y_j < Y_i$ を満たす $j \: (1 \leq j \leq N, j \neq i)$ が存在すること

である。

つまり、 $x$ 座標が小さい点の中に自身より $y$ 座標も小さい点があるかを判定すればよい。

$x$ 座標の値は順列なので、 $x = 1, 2, \cdots, N$ の順に見ていき、その時点までの最小の $y$ を持っておけば十分。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
6. 
7.constexpr int INF = 1e+9;
8. 
9.template <typename T>
10.inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
11. 
12.// ======================================== //
13. 
14.int main()
15.{
16.    int N;
17.    cin >> N;
18.    vector<int> YofX(N + 1);
19.    rep(i, 0, N) {
20.        int X, Y;
21.        cin >> X >> Y;
22.        YofX[X] = Y;
23.    }
24. 
25.    int Y_min = INF;
26.    int ans = 0;
27.    repe(x, 1, N) {
28.        int y = YofX[x];
29. 
30.        if (y < Y_min) {
31.            ans++;
32.        }
33. 
34.        chmin(Y_min, y);
35.    }
36. 
37.    cout << ans << endl;
38. 
39.    return 0;
40.}

https://atcoder.jp/contests/abc462/submissions/76630403

実装時間: 10 分

コメント

300点問題にしては比較的簡単だった。