528 b 区間スケジューリング 貪欲法 codeforces 最大クリーク問題

CodeForces 528 B. Clique Problem

CodeForces 528 B. Clique Problem
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://codeforces.com/contest/528/problem/B

一直線上に並んだ$N$個の点の座標$x_i$が与えられます.
お互いにある条件を満たす2つの点同士をすべてつなげる時、お互いに直接繋がった点の最大の点の数(いわゆる最大クリーク)を答える問題です.
条件とは、点$x_i$にはそれぞれ重み$w_i$が与えれていて、2点$x_i, x_j$が$|x_i - x_j| \geq w_i + w_j$を満たすことです.

入力

N
x_1 w_1
x_2 w_2
...
x_N w_N
  • N - 点の数($1 \leq N \leq 200000$).
  • x_i - 点の座標($0 \leq x_i 10^9$).
  • w_i - 点の重み($0 \leq w_i 10^9$).

出力

C

入出力例

4
2 3
3 1
6 1
0 2
3

解説

$N$が$2 \times 10^5$と大きいので計算量的に$O(N \log{N})$以下でないと間に合いません.
これはソート1回と線形探索1回が許される程度の計算量です.

問題文中でも言及されている通り、一般的な最大クリーク問題を多項式時間で解くのは難しそうです.
全探索で$2^N$で答えが求まりますがここではそれは使えません.

そこでこの問題における"重み"の意味を考えます.
よくあるグラフ問題の重みとは違って実はもっとシンプルなものであることが分かります.
例えば座標$10$で重み$5$の点であれば$10 \pm 5$の位置の点とは繋がらないということです.
つまりここでの"重み"とは長さのことです.
$10 - 5 = 5$を始点、$10 + 5 = 15$を終点とする線分として捉え直します.
"以上"なので始点と終端どちらかは含めませんので、ここでは終点を含まず$[5:15)$とします.
(整数でいうと$[5:14]$です.)

それを踏まえて上の入力例を見てみましょう.

まず1つ目の点です.

2 3

座標がxで重みが3です.
線分として捉えると始点-1、終点4の線分($[-1:5)$)です.
範囲$0 \leq x \leq 10^9$を超える場合はカットします.
始点0、終点4となります.

座標をo、それ以外の線分の部分を-で表してプロットすると以下のようになります.
0から7の番号は座標です.

   0 1 2 3 4 5 6 7
1: - - o - -

次に2つ目の点です.

3 1

線分として捉え直すと、始点2、終点3です.
プロットすると、

   0 1 2 3 4 5 6 7
1: - - o - -
2:     - o

3つ目、4つ目も同様に線分として捉える直すとそれぞれ$[5:6]$、$[0:1]$です.
プロットすると、

   0 1 2 3 4 5 6 7
1: - - o - -
2:     - o
3:           - o
4: o -

線分が重なっていないものは直接繋げられるということなので、答えは1以外の3点となります.

これを許容計算量であるソート+ 1回の走査で求めるには、まずすべての線分を終点が小さい順にソートします.
これは一番終端が小さい線分ほど他の線分と重なる可能性が低いからです.
より多くの点と繋がることが出来る可能性が高いからです.

上記の例ではこのようになります.

   0 1 2 3 4 5 6 7
4: o -
2:     - o
1: - - o - -
3:           - o

あとは先頭から見ていって最後に追加した線分と重なっていたら捨てる.
重なっていなかったら線分として追加する、ということを繰り返すだけです.

この走査が終わったら追加した線分の数が答えになります.

計算量

貪欲法のループは$O(N)$ですが、終端点による線分のソートに$O(N \log{N})$かかります.

$$
O(N \log{N})
$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define MAX_N 200000
#define MAX_X 1000000000
Int N;
vector<Segment> segments;

void input() {
  cin >> N;
  Int x_, w_;
  loop(n,0,N) {
    cin >> x_ >> w_;
    Int a = x_ - w_, b = x_ + w_ - 1; // [a:b)
    if (a < 0) a = 0;
    if (b > MAX_X) b = MAX_X;
    segments.push_back(Segment(a, b));
  }
}

void solve() {
  sort(span_all(segments));
  Int count = 0, right = -1;
  for (auto s: segments) {
    if (right < s.start) {
      count++;
      right = s.end;
    }
  }
  cout << count << endl;
}

int main() {
  input();
  solve();
  return 0;
}