2017 年の AGC の問題。現代なら ABC F で出そうだ。
問題概要
相異なる 
個の整数 
を 2 つのグループ X, Y に分けたい。
- グループ X では、どの 2 個の要素も差が
以下
- グループ Y では、どの 2 個の要素も差が
以下
となるようにする分け方は何通りあるか？ 1000000007 で割った余りを求めよ。
制約
考えたこと
この手の「どちらに振り分けるか」という選択を繰り返すような問題は、DP で解けることが多い。
今回は、各グループにすでに入っている数と新たに入れる数との差が 
以下であるかどうかを判定したいので、次のように DP を定義してみることにした。
dpX[i+1][j]：
の最初の 
個のみについて考える。それらを X, Y に振り分ける方法のうち、最後の要素 
を X に入れる方法であって、Y に入っているものの最大値が 
であるような方法の個数dpY[i+1][j]： の最初の 個のみについて考える。それらを X, Y に振り分ける方法のうち、最後の要素 を Y に入れる方法であって、X に入っているものの最大値が であるような方法の個数
DP の遷移を詰める
前回までの最後の要素が X 側で、新要素を X 側に入れるとき
のとき：dpX[i+1][j] += dpX[i][j]- そうでないとき：
dpX[i+1][j] = 0 ([tex: j = 0, 1, \dots, i-2)
前回までの最後の要素が Y 側で、新要素を Y 側に入れるとき
のとき：dpY[i+1][j] += dpY[i][j]- そうでないとき：
dpY[i+1][j] = 0 ([tex: j = 0, 1, \dots, i-2)
前回までの最後の要素が X 側で、新要素を Y 側に入れるとき
となる 
について
dpY[i+1][i-1] += dpX[i][j]
前回までの最後の要素が Y 側で、新要素を X 側に入れるとき
となる について
dpX[i+1][i-1] += dpY[i][j]
DP 高速化
上の DP は、in-place 化した上で、
- 区間 Change：区間 [l, r) の値をすべて x に更新する
- 区間和取得：区間 [l, r) の総和を求める
ができる遅延評価セグメント木を用いると、
の計算量で解ける。
......というのが、僕の AC した解法であった。
が、実は、区間 Change は必要なかった。僕は、in-place 化した配列 dp 上で dp[j] = 0 といった更新をする部分で、区間 Change をした。しかし、「最後に 0 にした箇所」を記録すれば、尺取法の要領で愚直に 0 にしていけばよいのだ。
コード
とはいえ、遅延評価セグメント木で殴るのは楽。ここでは遅延評価セグメント木で通したコードを。
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tint = array<int, 3>;
using tll = array<long long, 3>;
using fint = array<int, 4>;
using fll = array<long long, 4>;
using qint = array<int, 5>;
using qll = array<long long, 5>;
using sint = array<int, 6>;
using sll = array<long long, 6>;
using vint = vector<int>;
using vll = vector<long long>;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T_VAL, class T_MOD>
constexpr T_VAL mod_inv(T_VAL a, T_MOD m) {
T_VAL b = m, u = 1, v = 0;
while (b > 0) {
T_VAL t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
template<int MOD = 998244353, bool PRIME = true> struct Fp {
unsigned int val;
constexpr Fp() : val(0) { }
template<std::signed_integral T> constexpr Fp(T v) {
long long tmp = (long long)(v % (long long)(get_umod()));
if (tmp < 0) tmp += get_umod();
val = (unsigned int)(tmp);
}
template<std::unsigned_integral T> constexpr Fp(T v) {
val = (unsigned int)(v % get_umod());
}
constexpr long long get() const { return val; }
constexpr static int get_mod() { return MOD; }
constexpr static unsigned int get_umod() { return MOD; }
constexpr Fp operator + () const { return Fp(*this); }
constexpr Fp operator - () const { return Fp() - Fp(*this); }
constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; }
constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp &r) {
val += r.val;
if (val >= get_umod()) val -= get_umod();
return *this;
}
constexpr Fp& operator -= (const Fp &r) {
val -= r.val;
if (val >= get_umod()) val += get_umod();
return *this;
}
constexpr Fp& operator *= (const Fp &r) {
unsigned long long tmp = val;
tmp *= r.val;
val = (unsigned int)(tmp % get_umod());
return *this;
}
constexpr Fp& operator /= (const Fp &r) {
return *this = *this * r.inv();
}
constexpr Fp pow(long long n) const {
assert(n >= 0);
Fp res(1), mul(*this);
while (n) {
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
constexpr Fp inv() const {
if (PRIME) {
assert(val);
return pow(get_umod() - 2);
} else {
assert(val);
return mod_inv((long long)(val), get_umod());
}
}
constexpr bool operator == (const Fp &r) const {
return this->val == r.val;
}
constexpr bool operator != (const Fp &r) const {
return this->val != r.val;
}
constexpr bool operator < (const Fp &r) const {
return this->val < r.val;
}
constexpr bool operator > (const Fp &r) const {
return this->val > r.val;
}
constexpr bool operator <= (const Fp &r) const {
return this->val <= r.val;
}
constexpr bool operator >= (const Fp &r) const {
return this->val >= r.val;
}
constexpr Fp& operator ++ () {
++val;
if (val == get_umod()) val = 0;
return *this;
}
constexpr Fp& operator -- () {
if (val == 0) val = get_umod();
--val;
return *this;
}
constexpr Fp operator ++ (int) {
Fp res = *this;
++*this;
return res;
}
constexpr Fp operator -- (int) {
Fp res = *this;
--*this;
return res;
}
friend constexpr istream& operator >> (istream &is, Fp<MOD> &x) {
long long tmp = 1;
is >> tmp;
tmp = tmp % (long long)(get_umod());
if (tmp < 0) tmp += get_umod();
x.val = (unsigned int)(tmp);
return is;
}
friend constexpr ostream& operator << (ostream &os, const Fp<MOD> &x) {
return os << x.val;
}
friend constexpr Fp<MOD> pow(const Fp<MOD> &r, long long n) {
return r.pow(n);
}
friend constexpr Fp<MOD> inv(const Fp<MOD> &r) {
return r.inv();
}
};
template<class Monoid, class Action> struct LazySegmentTree {
using FuncMonoid = function<Monoid(Monoid, Monoid)>;
using FuncAction = function<Monoid(Action, Monoid)>;
using FuncComposition = function<Action(Action, Action)>;
int N;
FuncMonoid OP;
FuncAction ACT;
FuncComposition COMP;
Monoid IDENTITY_MONOID;
Action IDENTITY_ACTION;
int log, offset;
vector<Monoid> dat;
vector<Action> lazy;
LazySegmentTree() {}
LazySegmentTree(const FuncMonoid op, const FuncAction act, const FuncComposition comp,
const Monoid &identity_monoid, const Action &identity_action)
: OP(op), ACT(act), COMP(comp),
IDENTITY_MONOID(identity_monoid), IDENTITY_ACTION(identity_action) {}
LazySegmentTree(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp,
const Monoid &identity_monoid, const Action &identity_action) {
init(n, op, act, comp, identity_monoid, identity_action);
}
LazySegmentTree(const vector<Monoid> &v,
const FuncMonoid op, const FuncAction act, const FuncComposition comp,
const Monoid &identity_monoid, const Action &identity_action) {
init(v, op, act, comp, identity_monoid, identity_action);
}
void init(const FuncMonoid op, const FuncAction act, const FuncComposition comp,
const Monoid &identity_monoid, const Action &identity_action) {
OP = op, ACT = act, COMP = comp;
IDENTITY_MONOID = identity_monoid, IDENTITY_ACTION = identity_action;
}
void init(int n) {
N = n,
log = 0, offset = 1;
while (offset < N) ++log, offset <<= 1;
dat.assign(offset * 2, IDENTITY_MONOID);
lazy.assign(offset * 2, IDENTITY_ACTION);
}
void init(const vector<Monoid> &v) {
init((int)v.size());
build(v);
}
void init(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp,
const Monoid &identity_monoid, const Action &identity_action) {
init(op, act, comp, identity_monoid, identity_action);
init(n);
}
void init(const vector<Monoid> &v,
const FuncMonoid op, const FuncAction act, const FuncComposition comp,
const Monoid &identity_monoid, const Action &identity_action) {
init((int)v.size(), op, act, comp, identity_monoid, identity_action);
build(v);
}
void build(const vector<Monoid> &v) {
assert(N == (int)v.size());
for (int i = 0; i < N; ++i) dat[i + offset] = v[i];
for (int k = offset - 1; k > 0; --k) pull_dat(k);
}
int size() const {
return N;
}
void pull_dat(int k) {
dat[k] = OP(dat[k * 2], dat[k * 2 + 1]);
}
void apply_lazy(int k, const Action &f) {
dat[k] = ACT(f, dat[k]);
if (k < offset) lazy[k] = COMP(f, lazy[k]);
}
void push_lazy(int k) {
apply_lazy(k * 2, lazy[k]);
apply_lazy(k * 2 + 1, lazy[k]);
lazy[k] = IDENTITY_ACTION;
}
void pull_dat_deep(int k) {
for (int h = 1; h <= log; ++h) pull_dat(k >> h);
}
void push_lazy_deep(int k) {
for (int h = log; h >= 1; --h) push_lazy(k >> h);
}
void set(int i, const Monoid &v) {
assert(0 <= i && i < N);
int k = i + offset;
push_lazy_deep(k);
dat[k] = v;
pull_dat_deep(k);
}
Monoid get(int i) {
assert(0 <= i && i < N);
int k = i + offset;
push_lazy_deep(k);
return dat[k];
}
Monoid operator [] (int i) {
return get(i);
}
void apply(int i, const Action &f) {
assert(0 <= i && i < N);
int k = i + offset;
push_lazy_deep(k);
dat[k] = ACT(f, dat[k]);
pull_dat_deep(k);
}
void apply(int l, int r, const Action &f) {
assert(0 <= l && l <= r && r <= N);
if (l == r) return;
l += offset, r += offset;
for (int h = log; h >= 1; --h) {
if (((l >> h) << h) != l) push_lazy(l >> h);
if (((r >> h) << h) != r) push_lazy((r - 1) >> h);
}
int original_l = l, original_r = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) apply_lazy(l++, f);
if (r & 1) apply_lazy(--r, f);
}
l = original_l, r = original_r;
for (int h = 1; h <= log; ++h) {
if (((l >> h) << h) != l) pull_dat(l >> h);
if (((r >> h) << h) != r) pull_dat((r - 1) >> h);
}
}
Monoid prod(int l, int r) {
assert(0 <= l && l <= r && r <= N);
if (l == r) return IDENTITY_MONOID;
l += offset, r += offset;
for (int h = log; h >= 1; --h) {
if (((l >> h) << h) != l) push_lazy(l >> h);
if (((r >> h) << h) != r) push_lazy(r >> h);
}
Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) val_left = OP(val_left, dat[l++]);
if (r & 1) val_right = OP(dat[--r], val_right);
}
return OP(val_left, val_right);
}
Monoid all_prod() {
return dat[1];
}
int max_right(const function<bool(Monoid)> f, int l = 0) {
if (l == N) return N;
l += offset;
push_lazy_deep(l);
Monoid sum = IDENTITY_MONOID;
do {
while (l % 2 == 0) l >>= 1;
if (!f(OP(sum, dat[l]))) {
while (l < offset) {
push_lazy(l);
l = l * 2;
if (f(OP(sum, dat[l]))) {
sum = OP(sum, dat[l]);
++l;
}
}
return l - offset;
}
sum = OP(sum, dat[l]);
++l;
} while ((l & -l) != l);
return N;
}
int min_left(const function<bool(Monoid)> f, int r = -1) {
if (r == 0) return 0;
if (r == -1) r = N;
r += offset;
push_lazy_deep(r - 1);
Monoid sum = IDENTITY_MONOID;
do {
--r;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(OP(dat[r], sum))) {
while (r < offset) {
push_lazy(r);
r = r * 2 + 1;
if (f(OP(dat[r], sum))) {
sum = OP(dat[r], sum);
--r;
}
}
return r + 1 - offset;
}
sum = OP(dat[r], sum);
} while ((r & -r) != r);
return 0;
}
friend ostream& operator << (ostream &s, LazySegmentTree seg) {
for (int i = 0; i < (int)seg.size(); ++i) {
s << seg[i];
if (i != (int)seg.size() - 1) s << " ";
}
return s;
}
void dump() {
for (int i = 0; i <= log; ++i) {
for (int j = (1 << i); j < (1 << (i + 1)); ++j) {
cout << "{" << dat[j] << "," << lazy[j] << "} ";
}
cout << endl;
}
}
};
template<class Monoid> auto seg_op_add_with_sum = [](pair<Monoid, long long> p, pair<Monoid, long long> q) {
return make_pair(p.first + q.first, p.second + q.second);
};
template<class Monoid, class Action> auto seg_act_change_with_sum = [](Action f, pair<Monoid, long long> x) {
return (f != Action(-1) ? make_pair(f * x.second, x.second) : x);
};
template<class Action> auto seg_comp_change = [](Action g, Action f) {
return (g != Action(-1) ? g : f);
};
template<class Monoid, class Action> LazySegmentTree<pair<Monoid, long long>, Action> RangeChangeRangeSum(int N = 0) {
return LazySegmentTree<pair<Monoid, long long>, Action>(
N, seg_op_add_with_sum<Monoid>, seg_act_change_with_sum<Monoid, Action>, seg_comp_change<Action>,
make_pair(Monoid(0), 1), Action(-1));
};
int main() {
const ll MOD = 1000000007, INF = 1LL << 61;
using mint = Fp<MOD>;
ll N, A, B;
cin >> N >> A >> B;
deque<ll> S(N);
REP(i, N) cin >> S[i];
S.push_front(-INF);
N = S.size();
auto dpA = RangeChangeRangeSum<mint, mint>(N+1), dpB = RangeChangeRangeSum<mint, mint>(N+1);
dpA.apply(0, mint(1)), dpB.apply(0, mint(1));
REP2(i, 2, N) {
int it = upper_bound(ALL(S), S[i] - B) - S.begin();
chmin(it, i-1);
dpB.apply(i-1, dpA.prod(0, it).first);
it = upper_bound(ALL(S), S[i] - A) - S.begin();
chmin(it, i-1);
dpA.apply(i-1, dpB.prod(0, it).first);
if (S[i] - S[i-1] < A) dpA.apply(0, i-1, mint(0));
if (S[i] - S[i-1] < B) dpB.apply(0, i-1, mint(0));
}
mint res = dpA.all_prod().first + dpB.all_prod().first;
cout << res << endl;
}
を引く (ただし、負になる場合にはこの操作はできない)
のとき：既存の数列
が末尾に加わる
のとき：既存の数列
