問
数列 a が与えられる。a は以下の条件を満たしていることが保証されている。
- 任意の i について、
次のような数列 b を作りたい。
- b は部分列として a を含む（連続でなくても良い）
- b における任意の連続部分列の和は
以下である。つまり 
I1: b の最短の長さを求めよ。
I2: 最短の長さのbは何通りあるか998244353で割った余りを求めよ。（同じ b でも異なるインデックスの選び方の部分列でaが存在するなら、異なるものとしてカウントする）
解法
連続部分列の和が
となるような b ができる。さらに b のprefix sum は 0 以上 以下であることが分かる。
動的計画法を考えて、その特徴からスピードアップできることが分かる。
dp(i, s, p) :=
- a の接頭のi要素を使って bの接頭を作っていて
- bの接頭の和はsで
- pが0ならi要素を見た直後、pが1なら追加で新しい要素を入れるか検討した後
- そのときの最短の長さ
s < 0 または < s の場合は最短は存在しないので無限大として良い。
dp(i, s, 0) から dp(i, s', 1) の遷移を考えると、末尾に適切な1要素を追加することで dp(i, s', 1) は dp(i, *, 0)の最小値プラス1以下に出来る。さらにdp(i, *, 1) の最小値の範囲は連続している。
解 I1: このdpテーブルのdp(n, sumA, 1)が求めるべき解であるが、求めるには途中の最小値の値とその範囲だけ計算すれば良い。
解 I2: このdpテーブルで最短を計算していたが（最短, 場合の数) を計算することにする。dp(i, *, 1) を Run-length で持てば良い。区間に加算する必要があるので差分を持つことにして回避する。
======
コード
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
#define rprintf(fmt, begin, end) do { const auto end_rp = (end); auto it_rp = (begin); for (bool sp_rp=0; it_rp!=end_rp; ++it_rp) { if (sp_rp) putchar(' '); else sp_rp = true; printf(fmt, *it_rp); } putchar('\n'); } while(0)
int N;
int A[3000011];
void MAIN() {
scanf("%d", &N);
REP (i, N) scanf("%d", A+i);
LL target = 0;
REP (i, N) target += A[i];
LL l = 0, r = 0;
int cost = 0;
REP (i, N) {
l += A[i];
r += A[i];
if (l <= target && 0 <= r) {
amax(l, 0LL);
amin(r, target);
} else if (r < 0) {
l = 0;
r = target + A[i];
cost++;
} else {
assert(target < l);
l = A[i];
r = target;
cost++;
}
}
cost += N;
if (r < target) {
cost++;
}
printf("%d\n", cost);
}
int main() {
int TC = 1;
scanf("%d", &TC);
REP (tc, TC) MAIN();
return 0;
}
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
#define rprintf(fmt, begin, end) do { const auto end_rp = (end); auto it_rp = (begin); for (bool sp_rp=0; it_rp!=end_rp; ++it_rp) { if (sp_rp) putchar(' '); else sp_rp = true; printf(fmt, *it_rp); } putchar('\n'); } while(0)
template<unsigned MOD_> struct ModInt {
static constexpr unsigned MOD = MOD_;
unsigned x;
void undef() { x = (unsigned)-1; }
bool isnan() const { return x == (unsigned)-1; }
inline int geti() const { return (int)x; }
ModInt() { x = 0; }
ModInt(int y) { if (y<0 || (int)MOD<=y) y %= (int)MOD; if (y<0) y += MOD; x=y; }
ModInt(unsigned y) { if (MOD<=y) x = y % MOD; else x = y; }
ModInt(long long y) { if (y<0 || MOD<=y) y %= MOD; if (y<0) y += MOD; x=y; }
ModInt(unsigned long long y) { if (MOD<=y) x = y % MOD; else x = y; }
ModInt &operator+=(const ModInt y) { if ((x += y.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(const ModInt y) { if ((x -= y.x) & (1u<<31)) x += MOD; return *this; }
ModInt &operator*=(const ModInt y) { x = (unsigned long long)x * y.x % MOD; return *this; }
ModInt &operator/=(const ModInt y) { x = (unsigned long long)x * y.inv().x % MOD; return *this; }
ModInt operator-() const { return (x ? MOD-x: 0); }
ModInt inv() const { return pow(MOD-2); }
ModInt pow(long long y) const {
ModInt b = *this, r = 1;
if (y < 0) { b = b.inv(); y = -y; }
for (; y; y>>=1) {
if (y&1) r *= b;
b *= b;
}
return r;
}
friend ModInt operator+(ModInt x, const ModInt y) { return x += y; }
friend ModInt operator-(ModInt x, const ModInt y) { return x -= y; }
friend ModInt operator*(ModInt x, const ModInt y) { return x *= y; }
friend ModInt operator/(ModInt x, const ModInt y) { return x *= y.inv(); }
friend bool operator<(const ModInt x, const ModInt y) { return x.x < y.x; }
friend bool operator==(const ModInt x, const ModInt y) { return x.x == y.x; }
friend bool operator!=(const ModInt x, const ModInt y) { return x.x != y.x; }
};
constexpr LL MOD = 998244353;
using Mint = ModInt<MOD>;
struct Elem {
LL len;
int cost;
Mint value;
Elem() {}
Elem(LL len_, int cost_, Mint value_): len(len_), cost(cost_), value(value_) {}
};
deque<Elem> dq;
Mint C[3000011];
Mint offset[3000011];
void right_delete(LL n) {
while (n) {
int cost = dq.back().cost;
Mint value = dq.back().value;
LL g = min(n, dq.back().len);
C[cost] -= g * (value + offset[cost]);
dq.back().len -= g;
n -= g;
if (dq.back().len == 0) {
dq.pop_back();
}
}
}
void left_delete(LL n) {
while (n) {
int cost = dq.front().cost;
Mint value = dq.front().value;
LL g = min(n, dq.front().len);
C[cost] -= g * (value + offset[cost]);
dq.front().len -= g;
n -= g;
if (dq.front().len == 0) {
dq.pop_front();
}
}
}
int N;
int A[3000011];
void MAIN() {
dq.clear();
scanf("%d", &N);
REP (i, N) scanf("%d", A+i);
LL target = 0;
REP (i, N) target += A[i];
LL l = 0, r = 0;
int cost = 0;
dq.emplace_back(1, 0, Mint(1) - offset[0]);
C[0] = 1;
if (target) {
dq.emplace_back(target, 1, Mint(1) - offset[1]);
C[1] = target;
}
REP (i, N) {
if (A[i] > 0) {
LL a = A[i];
right_delete(a);
if (target < l + a) {
assert(C[cost] == 0);
cost++;
C[cost+1] = 0;
l = a;
r = target;
} else {
l += a;
r = min(r + a, target);
}
dq.emplace_front(a, cost + 1, -offset[cost + 1]);
}
if (A[i] < 0) {
LL a = -A[i];
left_delete(a);
if (r - a < 0) {
cost++;
C[cost+1] = 0;
l = 0;
r = target - a;
} else {
r -= a;
l = max(0LL, l - a);
}
dq.emplace_back(a, cost + 1, -offset[cost + 1]);
}
offset[cost + 1] += C[cost];
C[cost + 1] += C[cost] * ((target + 1) - (r - l + 1));
}
Mint ans = dq.back().value + offset[dq.back().cost];
printf("%d\n", ans.geti());
}
int main() {
int TC = 1;
scanf("%d", &TC);
REP (tc, TC) MAIN();
return 0;
}
と
の間で通常の二分探索を行う。
が100,000 以上になる最小の非負整数 x を求めよ。
について、dict に
なので 全体として
のとき：二分探索に近い
のとき：線形探索に近い
