AtCoder Grand Contest 009 C - Division into Two

C - Division into Two

問題

大きさ $n$ の整数からなる集合 $\{ s_1, \cdots, s_n \}$ が与えられる. これを以下の条件を満たすように 2 つの集合 $X, Y$ に分割する方法の数を求めよ.

  • $X$ に属する任意の異なる 2 要素について,その差の絶対値は $a$ 以上.
  • $Y$ に属する任意の異なる 2 要素について,その差の絶対値は $b$ 以上.

制約

  • $1 \leq n \leq 10^5$
  • $1 \leq a, b \leq 10^{18}$
  • $0 \leq s_1 \lt \cdots \lt s_n \leq 10^{18}$

考察

以下 $a \geq b$ として一般性を失わない.

$dp_i =$ 「 $\{ s_1, \cdots, s_i \}$ を $s_i$ が $X$ に属するように分割する場合の数」とする. これを直前に $X$ に属する要素 $j$ によって場合分けして求める.

まずこの $j$ が満たすべき条件として以下の 2 つがある.

  • $s_i - s_j \geq a$
  • $s_{k + 1} - s_{k} \geq b$ $(j \lt k, k + 1 \lt i)$

前者を満たさ ない 最小の $j$ を $r$ ,後者を満たす最小の $j$ を $l$ とする.前者はupper_bound()を使って,後者は前計算で前から求めていくことで十分高速に求まる.

このとき 基本的に $j \in [l, r)$ を直前に $X$ に属する要素として選べる. 強調したように,上の 2 つは十分条件ではない. 実際,唯一の反例として $s_j \in X$ で $s_{j + 1} - s_{j - 1} \lt b$ のケースがある.

ただ「基本的に」といったように, $j \in (l, r)$ ならこのようなことは起こらない ($\because s_{j + 1} - s_{j - 1} \geq s_{j + 1} - s_j \geq b$).

よって $j = l$ のときを考える. $s_{l + 1} - s_{l - 1} \lt b$ のとき, $s_l \in X$ なら $s_{l - 1} \not \in X$ となる $(\because s_l - s_{l - 1} \lt s_{l + 1} - s_{l - 1} \lt b \leq a)$ . ここから,「 $s_{l + 1} - s_{l - 1} \lt b$ 」と「 $j = l$ とできるか」が同値となる.

これで $j$ として選べる値の範囲が分かったので, $dp_i = \sum_{j = l}^{r - 1} dp_j$ と更新すればいい. これはセグ木か累積和で十分高速にできる.

最後に答えだが,「 $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;
}
Built with Hugo
テーマ StackJimmy によって設計されています。