C - Division into Two
問題
大きさ n の整数からなる集合 {s1,⋯,sn} が与えられる．
これを以下の条件を満たすように 2 つの集合 X,Y に分割する方法の数を求めよ．
- X に属する任意の異なる 2 要素について，その差の絶対値は a 以上．
- Y に属する任意の異なる 2 要素について，その差の絶対値は b 以上．
制約
- 1≤n≤105
- 1≤a,b≤1018
- 0≤s1<⋯<sn≤1018
考察
以下 a≥b として一般性を失わない．
dpi= 「 {s1,⋯,si} を si が X に属するように分割する場合の数」とする．
これを直前に X に属する要素 j によって場合分けして求める．
まずこの j が満たすべき条件として以下の 2 つがある．
- si−sj≥a
- sk+1−sk≥b (j<k,k+1<i)
前者を満たさ ない 最小の j を r ，後者を満たす最小の j を l とする．前者はupper_bound()を使って，後者は前計算で前から求めていくことで十分高速に求まる．
このとき 基本的に j∈[l,r) を直前に X に属する要素として選べる．
強調したように，上の 2 つは十分条件ではない．
実際，唯一の反例として sj∈X で sj+1−sj−1<b のケースがある．
ただ「基本的に」といったように， j∈(l,r) ならこのようなことは起こらない (∵sj+1−sj−1≥sj+1−sj≥b)．
よって j=l のときを考える．
sl+1−sl−1<b のとき， sl∈X なら sl−1∈X となる (∵sl−sl−1<sl+1−sl−1<b≤a) ．
ここから，「 sl+1−sl−1<b 」と「 j=l とできるか」が同値となる．
これで j として選べる値の範囲が分かったので， dpi=∑j=lr−1dpj と更新すればいい．
これはセグ木か累積和で十分高速にできる．
最後に答えだが，「 X に属する一番最後の値になりうる範囲」は上の l を求めるのと全く同じ要領でできるので，そこから後ろの和を出力すればいい．
実装例
初期条件を真面目に考えたり全部 Y に入っているケースがあったりして，考察を詰め切るのが結構難しい．
提出 #8119505 - AtCoder Grand Contest 009
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <limits>
template <int MOD>
class ModInt { ... };
template <class Data, class Operator>
class SegmentTree { ... };
using lint = long long;
constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;
int main() {
int n;
lint a, b;
std::cin >> n >> a >> b;
if (a < b) std::swap(a, b);
// a >= b
std::vector<lint> s(n);
for (auto& x : s) std::cin >> x;
std::vector<int> prevb(n);
// [j, i]の任意の要素の差がb以上な最小のj
prevb[0] = 0;
for (int i = 1; i < n; ++i) {
prevb[i] = (s[i] - s[i - 1] >= b ? prevb[i - 1] : i);
}
SegmentTree<mint, mint> seg(
n, 0,
[](mint a, mint b) { return a + b; },
[](mint e, mint a) { return a + e; });
// iがXに属する場合の数
seg.update(0, 1);
for (int i = 1; i < n; ++i) {
int l = prevb[i - 1];
int r = std::upper_bound(s.begin(), s.end(), s[i] - a) - s.begin();
if (l - 2 < 0 || s[l] - s[l - 2] >= b) --l;
// [l, r)を直前のXに属する要素として選択可能
seg.update(i, seg.query(l, r));
if (prevb[i - 1] == 0) {
// [0, i)を全部Yに，iをXに入れられる
seg.update(i, 1);
}
}
// 最後のAに属する要素が置かれうる範囲
int l = prevb[n - 1];
if (l - 2 < 0 || s[l] - s[l - 2] >= b) --l;
mint ans = seg.query(l, n);
// 全部Yに入るケース
if (l < 0) ++ans;
std::cout << ans << std::endl;
return 0;
}
|