コンテンツにスキップ

累積和

タグ「累積和」の記事 13 件

多角形のモーメントとは何か

shogo-library の多角形のライブラリには、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。

数直線上に、重さ m1,m2,…,mnm_1, m_2, \dots, m_n のおもりが位置 x1,x2,…,xnx_1, x_2, \dots, x_n に置かれているとします。このとき

  • 零次モーメント:M0=∑imiM_0 = \sum_i m_i(重さの合計)
  • 一次モーメント:M1=∑imixiM_1 = \sum_i m_i x_i(重さ × 位置の合計)
  • 二次モーメント:M2=∑imixi2M_2 = \sum_i m_i x_i^2(重さ × 位置の 2 乗の合計)

をモーメントと呼びます。kk 次モーメントは「重さ × 位置の kk 乗」の合計です。

重心(重さの平均位置)は g=M1/M0g = M_1 / M_0 です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。

名前の由来はてこです。位置 cc を支点にすると、おもり ii が回そうとする強さ(力のモーメント)は mi(xi−c)m_i (x_i - c) で、合計は M1−cM0M_1 - c M_0 です。これが 00 になる、つまり釣り合う支点が c=M1/M0c = M_1 / M_0、すなわち重心です。

平面の図形 DD では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。

S=∬D1 dA,Mx=∬Dx dA,My=∬Dy dAS = \iint_D 1 \, dA, \qquad M_x = \iint_D x \, dA, \qquad M_y = \iint_D y \, dA

SS は面積(零次モーメント)、(Mx,My)(M_x, M_y) は一次モーメントです。図形の重心は

(gx,gy)=(MxS,MyS)(g_x, g_y) = \left( \frac{M_x}{S}, \frac{M_y}{S} \right)

です。言いかえると、一次モーメントは「面積 × 重心」です:(Mx,My)=S⋅(gx,gy)(M_x, M_y) = S \cdot (g_x, g_y)。

モーメントは足せる、重心は足せない

Section titled “モーメントは足せる、重心は足せない”

モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになることです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。

一方、重心はそのままでは足せません。図形 AA と BB をくっつけた図形の重心は、AA の重心と BB の重心の平均ではなく、面積で重みを付けた平均

g=SAgA+SBgBSA+SBg = \frac{S_A g_A + S_B g_B}{S_A + S_B}

です。分子は一次モーメントの和、分母は面積の和なので、これは「モーメントを足してから割る」と言っているだけです。

例として、L 字形の図形 (0,0),(2,0),(2,1),(1,1),(1,2),(0,2)(0,0), (2,0), (2,1), (1,1), (1,2), (0,2) の重心を求めます。

  • 下の長方形 [0,2]×[0,1][0,2] \times [0,1]:S=2S = 2、重心 (1,0.5)(1, 0.5)、一次モーメント (2,1)(2, 1)
  • 左上の長方形 [0,1]×[1,2][0,1] \times [1,2]:S=1S = 1、重心 (0.5,1.5)(0.5, 1.5)、一次モーメント (0.5,1.5)(0.5, 1.5)

足すと S=3S = 3、一次モーメント (2.5,2.5)(2.5, 2.5) なので、重心は (2.5/3,2.5/3)=(5/6,5/6)(2.5/3, 2.5/3) = (5/6, 5/6) です。

引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができることが、あとで累積和に載せるときに効いてきます。

多角形のモーメントを辺ごとに分解する

Section titled “多角形のモーメントを辺ごとに分解する”

三角形 a,b,ca, b, c の面積は外積で S=12(b−a)×(c−a)S = \frac{1}{2} (b - a) \times (c - a)、重心は 3 頂点の平均 a+b+c3\frac{a + b + c}{3} です。したがって一次モーメントは

S⋅a+b+c3S \cdot \frac{a + b + c}{3}

です。

原点を頂点にした三角形に分ける

Section titled “原点を頂点にした三角形に分ける”

反時計回りの多角形 p0,p1,…,pn−1p_0, p_1, \dots, p_{n-1} を、辺 pi→pi+1p_i \to p_{i+1} ごとに原点 OO と結んだ三角形 O,pi,pi+1O, p_i, p_{i+1} に分けます(pn=p0p_n = p_0)。この三角形の符号付き面積は 12 pi×pi+1\frac{1}{2} \, p_i \times p_{i+1} で、OO から見て反時計回りなら正、時計回りなら負です。

O p₀ p₁ p₂ p₃
青は正(反時計回り)の三角形、赤は負(時計回り)の三角形。太線が多角形。

図では Op0p1O p_0 p_1, Op1p2O p_1 p_2, Op2p3O p_2 p_3 の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 Op3p0O p_3 p_0 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。

面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 O,pi,pi+1O, p_i, p_{i+1} の重心は pi+pi+13\frac{p_i + p_{i+1}}{3} なので、多角形全体は

S=12∑ipi×pi+1,(Mx,My)=16∑i(pi×pi+1)(pi+pi+1)S = \frac{1}{2} \sum_i p_i \times p_{i+1}, \qquad (M_x, M_y) = \frac{1}{6} \sum_i (p_i \times p_{i+1}) (p_i + p_{i+1})

となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。

polygon_edge_moment(p, q) は、辺 p→qp \to q の寄与(三角形 O,p,qO, p, q の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。

メンバ中身式
area2面積の 2 倍p×qp \times q
mxxx の一次モーメントの 6 倍(p×q)(px+qx)(p \times q)(p_x + q_x)
myyy の一次モーメントの 6 倍(p×q)(py+qy)(p \times q)(p_y + q_y)

全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は

gx=MxS=mx/6area2/2=mx3⋅area2g_x = \frac{M_x}{S} = \frac{\texttt{mx} / 6}{\texttt{area2} / 2} = \frac{\texttt{mx}}{3 \cdot \texttt{area2}}

を計算しています(gyg_y も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。

さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は

辺area2mxmy
(0,0)→(2,0)(0,0) \to (2,0)000
(2,0)→(2,1)(2,0) \to (2,1)282
(2,1)→(1,1)(2,1) \to (1,1)132
(1,1)→(1,2)(1,1) \to (1,2)123
(1,2)→(0,2)(1,2) \to (0,2)228
(0,2)→(0,0)(0,2) \to (0,0)000
合計61515

で、面積 6/2=36/2 = 3、重心 15/(3⋅6)=5/615 / (3 \cdot 6) = 5/6 と、長方形に分けて求めた結果と一致します。

座標が 10910^9 程度だと mx は 102710^{27} 程度になるので、整数座標のときは __int128_t で値を持ちます。

部分多角形の面積と重心を O(1)O(1) で求める

Section titled “部分多角形の面積と重心を O(1)O(1)O(1) で求める”

いちばんの使いみちです。多角形の頂点 u,u+1,…,vu, u+1, \dots, v を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。

部分多角形の辺は、元の多角形の辺 u→u+1,…,v−1→vu \to u+1, \dots, v-1 \to v と、閉じる辺 v→uv \to u です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で O(1)O(1) で求まり、そこに閉じる辺の寄与を 1 つ足せば完成です。PolygonMoment は + と - が使えるので、そのまま累積和に載せられます。頂点の番号が一周をまたぐ場合もあるので、円環上の区間和 CircularSum を使うと便利です。

using P = Vector<long long>;
std::vector<PolygonMoment<long long>> e(n);
for (int i = 0; i < n; i++) e[i] = polygon_edge_moment(ps[i], ps[(i + 1) % n]);
CircularSum cs(e);
// 頂点 u, u+1, ..., v を結んだ部分多角形
auto m = cs.sum(u, v) + polygon_edge_moment(ps[v], ps[u]);
m.area(); // 符号付き面積
m.centroid(); // 重心

辺の寄与は原点の位置によって変わりますが、閉じた多角形について足した合計は原点によりません(打ち消し合いの議論は原点の位置を問わないからです)。途中までの和だけでは意味のある値にならず、閉じる辺を足して初めて部分多角形の値になる、という点に注意してください。

凸多角形を対角線で 2 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が O(1)O(1) で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。

頂点 pip_i を動かすと、寄与が変わるのは辺 pi−1→pip_{i-1} \to p_i と pi→pi+1p_i \to p_{i+1} の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ O(log⁡n)O(\log n) でできます。

離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。

整数座標なら area2, mx, my はすべて整数で、重心は gx=mx/(3⋅area2)g_x = \texttt{mx} / (3 \cdot \texttt{area2}) という分数です。2 つの図形の重心の xx 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。

ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。

Ixx=∬Dx2 dA=112∑i(pi×pi+1)(xi2+xixi+1+xi+12)I_{xx} = \iint_D x^2 \, dA = \frac{1}{12} \sum_i (p_i \times p_{i+1}) (x_i^2 + x_i x_{i+1} + x_{i+1}^2)

(xix_i は pip_i の xx 座標。IyyI_{yy} も同様)。L 字形で計算すると Ixx=3I_{xx} = 3 になり、長方形ごとに積分した 83+13\frac{8}{3} + \frac{1}{3} と一致します。

二次モーメントがあると、たとえば図形内の一様ランダムな点と点 cc の距離の 2 乗の期待値が

Ixx+IyyS−2 c⋅g+∣c∣2\frac{I_{xx} + I_{yy}}{S} - 2 \, c \cdot g + |c|^2

で求まります。物理でいう慣性モーメント(回転させにくさ)も、この Ixx+IyyI_{xx} + I_{yy} です。

  • kk 次モーメントは「重さ × 位置の kk 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
  • モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
  • 多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
  • 寄与の累積和を取れば、部分多角形の面積と重心が O(1)O(1) で求まる。PolygonMoment はそのための型

repovive starter round 10 C - Museum Records

nn 人が博物館に 1 回ずつ入って出ました。2n2n 回の入退場の時刻はすべて異なります。各人 ii について、

  • aia_i:ii が入る前に出ていた人数
  • bib_i:ii が出たあとに入ってきた人数

が記録されています。すべての記録が正しくなる入退場の順番があるか判定する問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤ai,bi<n0 \le a_i, b_i < n)。

aia_i は、入るのが遅い人ほど大きいか等しいです。よって、入る順番は aia_i の昇順です。aia_i が等しい人どうしの間では誰も出ていないので、その人たちの入る順番を入れ替えても、ほかの人の a,ba, b は変わりません。

kk 人目が入ってから k+1k + 1 人目が入るまでの間を「すき間 kk」と呼びます(すき間 nn は最後の人が入ったあと)。bib_i 人があとから入ってくるので、人 ii はすき間 n−bin - b_i で出ます。同じすき間で出る人どうしの順番は、記録に影響しません。

こうして入退場の順番は(記録に影響しない入れ替えを除いて)決まるので、次の 2 つを満たすか調べれば十分です。人 ii が kik_i 番目に入るとします。

  1. 入ってから出る:ki≤n−bik_i \le n - b_i。
  2. aia_i が正しい:aia_i は、n−bj≤ki−1n - b_j \le k_i - 1 である人 jj の人数に等しい。

aia_i が等しい人どうしの順番は 2. に影響しないので、1. を満たしやすい順にします。それは bib_i の大きい人(早く出る人)を先にする順です。

aia_i の昇順、同じなら bib_i の降順に並べます。0-indexed で ii 番目の人は k=i+1k = i + 1 番目に入るので、1. は i+1≤n−bi + 1 \le n - b です。

また、2. の人数は、すき間ごとに出る人数を数えて累積和をとれば求まります。ckc_k を「すき間 kk 以下で出る人数」とすると、2. は a=cia = c_i です。

全員がこの 2 つを満たせば Yes、そうでなければ No です。計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n = int(input())
ab = [tuple(map(int, input().split())) for i in range(n)]
ab.sort(key=lambda x: (x[0], -x[1]))
c = [0] * (n + 1)
for a, b in ab:
c[n - b] += 1
for i in range(n):
c[i + 1] += c[i]
for i, (a, b) in enumerate(ab):
if i + 1 > n - b or a != c[i]:
print("No")
exit(0)
print("Yes")

ABC480 D - Concatenation of Prefixes

長さ NN の整数列 AA が与えられます。i=1,2,…,Ni = 1, 2, \dots, N の順に (A1,…,Ai)(A_1, \dots, A_i) を末尾に連結して、長さ N(N+1)2\frac{N(N+1)}{2} の数列 BB を作ります。QQ 個の質問 (L,R)(L, R) について、BL+⋯+BRB_L + \dots + B_R を求める問題です(1≤N,Q≤1051 \le N, Q \le 10^5、−108≤Ai≤108-10^8 \le A_i \le 10^8)。

BB の先頭からの和 f(x)=B1+⋯+Bxf(x) = B_1 + \dots + B_x が求められれば、答えは f(R)−f(L−1)f(R) - f(L - 1) です。

BB は、kk 番目のかたまりが (A1,…,Ak)(A_1, \dots, A_k) であるようなかたまりの連結です。kk 番目のかたまりの長さは kk なので、はじめの ii 個のかたまりの長さの合計は Ti=i(i+1)2T_i = \frac{i(i+1)}{2} です。また、AA の累積和を Pj=A1+⋯+AjP_j = A_1 + \dots + A_j とすると、kk 番目のかたまりの和は PkP_k です。

f(x)f(x) を求めるには、まず Ti≤xT_i \le x となる最大の ii を求めます。B1,…,BxB_1, \dots, B_x は、はじめの ii 個のかたまりと、i+1i + 1 番目のかたまりの先頭 x−Tix - T_i 個からなります。したがって

f(x)=(P1+⋯+Pi)+Px−Tif(x) = (P_1 + \dots + P_i) + P_{x - T_i}

です。PP と、PP の累積和を前計算しておけば、f(x)f(x) は ii を求めるだけで計算できます。TiT_i は増加列なので、ii は二分探索で求められます。

計算量は O(N+Qlog⁡N)O(N + Q \log N) です。∣f(x)∣|f(x)| は最大で N(N+1)2×108≈5×1017\frac{N(N+1)}{2} \times 10^8 \approx 5 \times 10^{17} 程度なので、64 ビット整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/binary-search.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, Q);
VL(A, N);
vl tmp = {0};
vl s0 = {0}, s1 = {0};
rep(i, N) {
s0.push_back(s0.back() + A[i]);
s1.push_back(s1.back() + s0.back());
tmp.push_back(tmp.back() + i + 1);
}
auto q = [&](ll x) {
ll i = bisect_right(tmp, x) - 1;
return s1[i] + s0[x - tmp[i]];
};
rep(Q) {
LL(L, R);
print(q(R) - q(L - 1));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tmp[i] が TiT_i、s0[j] が PjP_j、s1[i] が P1+⋯+PiP_1 + \dots + P_i です。bisect_right(tmp, x) は tmp の中で x より大きい最初の要素の位置(Python の bisect.bisect_right と同じ)を返すので、そこから 11 を引くと Ti≤xT_i \le x となる最大の ii になります。q(x) が f(x)f(x) です。

使用ライブラリ:cpp_include@9c33ee7

累積和・いもす法のリンク集

累積和といもす法について、参考になる記事や資料をまとめました。

累積和は、数列 a0,…,aN−1a_0, \dots, a_{N-1} に対して S0=0S_0 = 0、Si+1=Si+aiS_{i+1} = S_i + a_i を前計算しておき、区間 [l,r)[l, r) の和を Sr−SlS_r - S_l で O(1)O(1) で求める手法です。2 次元に広げると、長方形の範囲の和も 4 つの値の足し引きで求められます。

いもす法は、その逆の操作です。「区間 [l,r)[l, r) に xx を足す」を ll に +x+x、rr に −x-x と記録するだけで済ませ、最後に累積和をとって全体の値を一度に求めます。2 次元(長方形への加算)や、木の上(部分木への加算)にも使えます。

資料によって、区間を半開区間 [l,r)[l, r) で書くものと閉区間 [l,r][l, r] で書くものがあります。読み比べるときは、どちらの流儀かに気をつけてください。

  • 累積和を何も考えずに書けるようにする!(けんちょん、Qiita)
    • 半開区間と S0=0S_0 = 0 の流儀で 1 次元の累積和を丁寧に説明し、2 次元の累積和まで扱っています。例題 5 問の C++ の解答つきで、最後にいもす法やしゃくとり法などの発展の話題も紹介しています。
    • 2-1 節の検算で「s13=a1+⋯+a12s_{13} = a_1 + \dots + a_{12}」のように添字が 1 ずれています(定義どおりなら a0a_0 からの和です)。差をとった結果は正しいです。
  • 区間の和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 1 次元の累積和を、図を多く使って初心者向けに説明しています。C++ の実装と練習問題つきです。
  • 二次元での区間和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 2 次元の累積和の作り方と長方形の和の求め方を、たくさんの図で説明しています。
    • 最後の「更新がある場合」で 2 次元 BIT の計算量を O(log⁡HW)O(\log HW) としていますが、正しくは O(log⁡Hlog⁡W)O(\log H \log W) です。

コードは int で書かれているものが多いので、和が大きくなる問題では long long を使ってください。

  • いもす法(いもす研)
    • 考案者のいもすさんによる解説です。1 次元の基本から、2 次元、三角形・六角形の座標系、高次(2 次関数など)まで、図を多く使って説明しています。コードは C/C++ で、区間は半開区間です。英語版もあります。
    • 区間の右端 EiE_i が TT になり得るのに、配列を大きさ TT で扱っています。書き写すときは、配列を 1 つ大きく取ってください。
    • 2 次元の説明で、(Ai,Di)(A_i, D_i) を「右上」、(Bi,Ci)(B_i, C_i) を「左下」と呼んでいますが、コードの座標の向きでは逆です。どちらも −1-1 を足す点なので、結果は変わりません。
  • Pythonで累積和・累積積(itertools.accumulate)(note.nkmk.me)
    • itertools.accumulate の使い方の解説です。initial=0 を指定すると先頭に 00 がついた長さ N+1N + 1 の累積和になること、max や operator.mul を渡して累積 max や累積積を作れることが分かります。

木の上のいもす法を一般的に解説した定番の記事は見つからなかったので、問題の解説記事を挙げます。

  • AtCoder ABC 138 D - Ki(けんちょんの競プロ精進記録)
    • 部分木全体への加算を、根の頂点に記録しておき、最後に根から子へ値を配ることで O(N+Q)O(N + Q) にする方法です。配列のいもす法から順に木へ移していく流れで説明しています。コードは C++ の再帰 DFS です。
  • AtCoder ABC 187 E - Through Path(けんちょんの競プロ精進記録)
    • 「部分木の外への加算」を「全体に足して、部分木から引く」に言い換えて、上と同じ方法に帰着させています。
  • いもす法のカテゴリ(けんちょんの競プロ精進記録)
    • いもす法を使う問題の解説がまとまっていて、問題集としても使えます。

累積和・いもす法そのものを解説した講座はありません。

  • 転置原理入門
    • 転置原理の講座で、具体例として区間和クエリ(累積和)の解法を転置すると、区間加算クエリの解法が得られることを示しています。5.4 節で、それが imos 法であると紹介しています。累積和といもす法の関係を知りたい人向けの発展的な読み物で、累積和は前提知識として扱われています。
  • 累積和(日本語版 Wikipedia)、Prefix sum(英語版 Wikipedia)
    • 定義と、inclusive scan・exclusive scan の違い、並列計算での求め方が中心です。区間和を求める使い方の説明はほとんどないので、用語を確かめる程度に使ってください。いもす法(差分配列)の記事は日本語版・英語版ともにありません。
  • Summed-area table(英語版 Wikipedia)
    • 2 次元の累積和の記事で、画像処理(integral image)の文脈で書かれています。dd 次元への一般化の式も載っています。dd 次元の段落では、2 次元の段落と点の名前の付け方が入れ替わっています。
  • Introduction to Prefix Sums(USACO Guide)
    • 1 次元の累積和の入門で、C++・Java・Python のコードと練習問題の一覧があります。
    • 最初の Python のコードは psums[-1] を psum[-1] と書き間違えていて、そのままでは動きません。
  • More on Prefix Sums(USACO Guide)
    • 最大部分配列和、2 次元の累積和(構築の様子が見られる図つき)、差分配列(いもす法)を扱っています。区間は閉区間で書かれています。
  • An Introduction To Difference Arrays(arujbansal、Codeforces)
    • 1 次元の差分配列の短い入門です。閉区間 [L,R][L, R] で書いていて、配列を N+2N + 2 の大きさで取る理由も説明しています。

DOJ Beginner Contest 7 B - tourist vs rainboy

NN 問の問題が難しさの昇順に並んでいて、ii 番目の問題を解くには時間 AiA_i がかかります(A1≤A2≤⋯≤ANA_1 \le A_2 \le \dots \le A_N)。

tourist と rainboy は時刻 00 に解き始め、休まずに 1 問ずつ解いていきます。各問題を解き終えた時刻の和がペナルティです。tourist は 1,2,…,N1, 2, \dots, N 番の順に、rainboy は N,N−1,…,1N, N - 1, \dots, 1 番の順に解きます。rainboy のペナルティから tourist のペナルティを引いた値を求める問題です。

解く順に AA を並べたとき、kk 問目を解き終える時刻は、最初の kk 問にかかる時間の和(累積和)です。ペナルティはその累積和を全部足したものです。

  • tourist のペナルティは、AA を前から足していったときの累積和の合計です。
  • rainboy のペナルティは、AA を後ろから足していったときの累積和の合計です。

それぞれを O(N)O(N) で計算し、差をとります。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = 0
x = 0
for a in A:
x += a
ans -= x
x = 0
for a in reversed(A):
x += a
ans += x
print(ans)

x が今の累積和(解き終えた時刻)です。前から足すときは ans から引き、後ろから足すときは ans に加えることで、差を直接求めています。

SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain

正の整数の列 b1,…,bnb_1, \dots, b_n に対して、g(b)ig(b)_i を「ii より左にあって bj<bib_j < b_i を満たす jj のうち最大のもの(なければ 00)」と定めます。ある bb によって y=g(b)y = g(b) と書ける列 yy を「復元可能」と呼びます。

長さ nn の列 xx が与えられます。xx のいくつかの要素は −1-1 です。−1-1 をそれぞれ 00 以上 nn 以下の整数に置き換えて xx を復元可能にする方法の数を、109+710^9 + 7 で割った余りで求めてください(nn の総和 ≤5000\le 5000)。

bb の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1,…,n1, \dots, n で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。gg の定義が真の不等号 bj<bib_j < b_i なので、こうすると「bj<bib_j < b_i」と「jj のほうが小さい(j<ij < i のとき)」が一致します。

このとき、ii の左部分木はちょうど区間 [gi+1,i−1][g_i + 1, i - 1] になります。ii の左部分木は「ii から左へ、ii より大きい要素が続く範囲」で、その左端の外側が ii より左で最も近い小さい要素、つまり gig_i だからです。

gg とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。

  • 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
  • ii を追加するときは、bib_i より大きい要素をスタックから pop する。pop した部分が ii の左部分木になり、ii は残ったスタックの一番上の右の子になる。最後に ii を push する

pop し終わったときのスタックの一番上が、ちょうど gig_i です(空なら 00)。そのため、各ステップで何個 pop するかは gg から決まり、ツリーの形も gg から決まります。逆に、どんな形のツリーにも、それを作る bb が存在します(例えば、根からの深さをそのまま bb にすればよいです)。

まとめると、復元可能な yy と、nn 頂点の二分木の形は一対一に対応します。全部が −1-1 のときの答えは Catalan 数 CnC_n で、サンプル 3 の 132=C6132 = C_6 と一致します。

例えば g=[0,1,2,1,0,0,6]g = [0, 1, 2, 1, 0, 0, 6] に対応するツリーの親は、[5,4,2,1,6,−,6][5, 4, 2, 1, 6, -, 6] です(6 が根)。4 の左部分木が [g4+1,3]=[2,3][g_4 + 1, 3] = [2, 3] になっていることなどが確かめられます。

この対応を使うと、問題は次のように言い換えられます。

頂点 1,…,n1, \dots, n を中間順に並べた二分木のうち、xi≠−1x_i \ne -1 であるすべての ii について「ii の左部分木がちょうど [xi+1,i−1][x_i + 1, i - 1] である」ものを数える

xi≥ix_i \ge i のときは、そのような左部分木はありえないので答えは 00 です。

固定された左部分木は独立に数えられる

Section titled “固定された左部分木は独立に数えられる”

xi≠−1x_i \ne -1 のとき、ii の左部分木 [xi+1,i−1][x_i + 1, i - 1] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと ii に潰してしまえば、ii は「左の子を持たない頂点」 として扱えます。

そこで、左から順に頂点を見ながら、次のように列を潰していきます。

  • xi=−1x_i = -1 のとき:ii を「自由な頂点」として列の末尾に加える
  • xi≠−1x_i \ne -1 のとき:列の中から xi+1x_i + 1 以降に始まる要素をすべて取り出す。それらが ii の左部分木になるので、その形の数を答えに掛ける。そのあと、xi+1x_i + 1 から ii までをまとめて「左の子を持たない頂点」1 個として末尾に加える

列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が xi+1x_i + 1 から始まる要素になっていないとき、つまり xi+1x_i + 1 がすでに潰された要素の内側にあるときは、答えは 00 です。ii の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。

最後に残った列全体の形の数も掛ければ、答えになります。

左の子を持たない頂点を含む二分木の数え上げ

Section titled “左の子を持たない頂点を含む二分木の数え上げ”

あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。

Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが hh のとき、次の頂点を追加する方法は次のとおりです。

  • 自由な頂点:00 個以上 hh 個以下を pop してから push するので、新しい高さは 11 以上 h+1h + 1 以下
  • 左の子を持たない頂点:pop しないで push するので、新しい高さは h+1h + 1

pop の仕方とツリーの形は一対一に対応するので、dp[h]\mathrm{dp}[h] を「スタックの高さが hh になる方法の数」とする DP で数えられます。自由な頂点の遷移は

dp′[h′]=∑h≥h′−1dp[h]\mathrm{dp}'[h'] = \sum_{h \ge h' - 1} \mathrm{dp}[h]

なので、後ろからの累積和で O(長さ)O(\text{長さ}) で計算できます。答えは最後の dp\mathrm{dp} の総和です。

各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ mm の列の DP は O(m2)O(m^2) なので、全体で O(n2)O(n^2) です。

Python
from bisect import bisect_left
from itertools import accumulate
MOD = 10**9 + 7
def count(flags):
dp = [1]
for f in flags:
if f:
dp = [0] + dp
else:
s = list(accumulate(reversed(dp)))
s.reverse()
dp = [0] + [v % MOD for v in s]
return sum(dp) % MOD
def solve(n, x):
ans = 1
starts = []
flags = []
for i in range(1, n + 1):
if x[i - 1] == -1:
starts.append(i)
flags.append(False)
continue
l = x[i - 1] + 1
if l > i:
return 0
k = bisect_left(starts, l)
if l < i and (k == len(starts) or starts[k] != l):
return 0
ans = ans * count(flags[k:]) % MOD
del starts[k:]
del flags[k:]
starts.append(l)
flags.append(True)
return ans * count(flags) % MOD
t = int(input())
for _ in range(t):
n = int(input())
x = list(map(int, input().split()))
print(solve(n, x))

starts は列の各要素が元の列のどこから始まるか、flags はその要素が左の子を持たない頂点かどうかです。starts は昇順なので、xi+1x_i + 1 から始まる要素を bisect_left で探しています。

count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。

SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R

長さ nn の数列 aa と整数 L,RL, R が与えられます。連続する部分列のうち、総和が LL 以上 RR 以下のものの個数を求める問題です(n≤105n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、−1014≤L≤R≤1014-10^{14} \le L \le R \le 10^{14})。aia_i は負になることもあります。

累積和を S0=0S_0 = 0、Sj=a1+⋯+ajS_j = a_1 + \cdots + a_j とすると、区間 [i+1,j][i + 1, j] の総和は Sj−SiS_j - S_i です。条件 L≤Sj−Si≤RL \le S_j - S_i \le R を SiS_i について書き直すと

Sj−R≤Si≤Sj−LS_j - R \le S_i \le S_j - L

です。したがって、各 jj について「i<ji < j で SiS_i が [Sj−R,Sj−L][S_j - R, S_j - L] に入るものの個数」を足し合わせれば答えになります。

aia_i が負になることもあるので SS は単調ではなく、しゃくとり法は使えません。そこで j=1,2,…,nj = 1, 2, \ldots, n の順に見ていき、それまでに出てきた SiS_i を、値ごとの個数として管理します。必要な操作は次の 2 つです。

  • SjS_j を 1 個追加する
  • 値が [Sj−R,Sj−L][S_j - R, S_j - L] の範囲にある SiS_i の個数を数える

SS の値は最大 101410^{14} 程度と大きいので、S0,…,SnS_0, \ldots, S_n を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 [Sj−R,Sj−L][S_j - R, S_j - L] は、圧縮後の添字では二分探索で求まります。全体で O(nlog⁡n)O(n \log n) です。

C++(セグメント木)
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
void solve() {
LL(N, L, R);
VL(A, N);
ll t = 0;
sl s;
s.insert(t);
for (ll a : A) {
t += a;
s.insert(t);
}
vl v(all(s));
RSumQ<ll> seg(v.size());
ll ans = 0;
t = 0;
seg.apply(bisect_left(v, t), 1);
for (ll a : A) {
t += a;
ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L));
seg.apply(bisect_left(v, t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 xx の添字は bisect_left(v, x) です。

後半では t が SjS_j で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が [Sj−R,Sj−L][S_j - R, S_j - L] にある SiS_i の個数」です。数えてから seg.apply(..., 1) で SjS_j を追加するので、i<ji < j のものだけが数えられます。RSumQ は区間和のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

Python(BIT)
from bisect import bisect_left, bisect_right
from itertools import accumulate
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
S = [0, *accumulate(A)]
v = sorted(set(S))
M = len(v)
bit = [0] * (M + 1)
def add(i):
i += 1
while i <= M:
bit[i] += 1
i += i & -i
def count(i):
res = 0
while i:
res += bit[i]
i -= i & -i
return res
ans = 0
add(bisect_left(v, 0))
for t in S[1:]:
ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R))
add(bisect_left(v, t))
print(ans)

C++ 版と同じ処理を BIT で書いています。count(i) は添字が ii 未満の個数なので、2 つの差が範囲内の個数になります。

SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K

長さ nn の数列 aa と整数 kk が与えられます。連続する部分列 al,…,ara_l, \ldots, a_r のうち、総和が kk で割り切れるものの個数を求める問題です(n≤105n \le 10^5、k≤109k \le 10^9、0≤ai≤1090 \le a_i \le 10^9)。

累積和を S0=0S_0 = 0、Si=a1+⋯+aiS_i = a_1 + \cdots + a_i とすると、区間 [l,r][l, r] の総和は Sr−Sl−1S_r - S_{l-1} です。これが kk で割り切れるのは

Sr≡Sl−1(modk)S_r \equiv S_{l-1} \pmod{k}

のときです。つまり、0≤i<j≤n0 \le i < j \le n で Si mod kS_i \bmod k と Sj mod kS_j \bmod k が等しい組 (i,j)(i, j) の個数が答えです。

j=0,1,…,nj = 0, 1, \ldots, n の順に見ていき、それまでに出てきた余りの個数を数えておけば、各 jj について「Sj mod kS_j \bmod k と同じ余りの SiS_i が前に何個あったか」がすぐに分かります。全体で O(n)O(n) です。

Python
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
t = 0
C = Counter()
C[0] += 1
ans = 0
for a in A:
t += a
t %= K
ans += C[t]
C[t] += 1
print(ans)

t が累積和を kk で割った余り、C が余りごとの出現回数です。最初に C[0] += 1 で S0=0S_0 = 0 の分を数えておき、各要素を足すたびに同じ余りの個数を答えに加えています。

kk は最大 10910^9 なので、配列ではなく Counter(辞書)で数えています。

ABC477 E - Wheel Distance

頂点 1,…,N1, \ldots, N が重み AiA_i の辺で円環状につながり、さらに各頂点 ii が中心の頂点 N+1N+1 と重み BiB_i の辺でつながったグラフがあります。QQ 個のクエリ (S,T)(S, T) それぞれについて、頂点 SS から頂点 TT への最短経路の長さを求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

中心の頂点を H=N+1H = N + 1 とし、HH から各頂点への最短距離 FvF_v をダイクストラ法で求めておきます。

T=HT = H のときは、答えは FSF_S です。

T≠HT \ne H のときは、最短経路が HH を通るかどうかで場合分けします。

  • HH を通る場合: SS から HH へ行き、HH から TT へ行く経路になるので、長さは FS+FTF_S + F_T 以上です。逆に、S→HS \to H と H→TH \to T の最短経路をつなげれば長さ FS+FTF_S + F_T の経路が作れます。なので、この場合の最短は FS+FTF_S + F_T です。
  • HH を通らない場合: 円環の上だけを通るので、SS から TT へ時計回りに行くか、反時計回りに行くかの 2 通りです。AA の累積和を Gi=A1+⋯+AiG_i = A_1 + \cdots + A_i とすると、長さはそれぞれ GT−1−GS−1G_{T-1} - G_{S-1} と GN−(GT−1−GS−1)G_N - (G_{T-1} - G_{S-1}) です。

この 3 つの最小値が答えです。前処理が O(Nlog⁡N)O(N \log N)、各クエリが O(1)O(1) です。

cLay
ll@N,@Q,@A[N],@B[N],E[2N],F[N+1],G[N+1]{};int C[2N],D[2N];rep(i,N)C[i]=i,D[i]=(i+1)%N,G[i+1]=G[i]+(E[i]=A[i]),C[N+i]=i,D[N+i]=N,E[N+i]=B[i];wgraph<ll>g;g.setEdge(N+1,2N,C,D,E);g.getDist(N,F);rep(Q){ll@S--,@T--,x;if(N-T)x=F[S]+F[T],x<?=G[T]-G[S],wt(x<?=G[S]+G[N]-G[T]);else wt(F[S]);}

cLay で書いています。頂点は 0 始まりで、0,…,N−10, \ldots, N-1 が円環、NN が中心です。

C、D、E に辺の両端と重みを入れ、wgraph の setEdge で重み付き無向グラフを作り、getDist(N, F) で中心からの最短距離を F に求めています。G は AA の累積和です。

クエリでは x<?= (小さい方を代入する cLay の演算子)で 3 つの候補の最小値をとっています。N-T が 00、つまり TT が中心のときは F[S] を出力します。

Python
from heapq import heappop, heappush
from itertools import accumulate
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for i in range(N):
graph[i].append(((i + 1) % N, A[i]))
graph[(i + 1) % N].append((i, A[i]))
graph[i].append((N, B[i]))
graph[N].append((i, B[i]))
F = [None] * (N + 1)
pq = [(0, N)]
while pq:
d, v = heappop(pq)
if F[v] is not None:
continue
F[v] = d
for u, w in graph[v]:
if F[u] is None:
heappush(pq, (d + w, u))
acc = [0, *accumulate(A)]
ans = []
for _ in range(Q):
S, T = map(int, input().split())
S -= 1
T -= 1
if T == N:
ans.append(F[S])
else:
ans.append(min(F[S] + F[T], acc[T] - acc[S], acc[S] + acc[N] - acc[T]))
print(*ans, sep="\n")

cLay 版と同じ処理です。ダイクストラ法は heapq で書いています。

ABC477 C - Range Search Query

文字列 S,TS, T が与えられます。QQ 個のクエリ (L,R)(L, R) それぞれについて、SS の LL 文字目から RR 文字目までの部分に TT が含まれるかを判定する問題です(∣S∣≤4×105|S| \le 4 \times 10^5、∣T∣≤10|T| \le 10、Q≤2×105Q \le 2 \times 10^5)。

SS の LL 文字目から RR 文字目までに TT が含まれるのは、TT が SS の ii 文字目から始まって出現するような ii が L≤i≤R−∣T∣+1L \le i \le R - |T| + 1 の範囲にあるときです。

そこで、前処理として SS の各位置から TT が始まるかを調べておきます。∣T∣≤10|T| \le 10 なので、各位置で愚直に比べても O(∣S∣∣T∣)O(|S||T|) で間に合います。これの累積和をとっておけば、各クエリでは区間 [L,R−∣T∣+1][L, R - |T| + 1] にある開始位置の個数が O(1)O(1) で求まり、それが 11 以上なら Yes です。

Python
Q = int(input())
S = input()
T = input()
N, M = len(S), len(T)
acc = [0] * (N + 1)
for i in range(N):
acc[i + 1] = acc[i] + S.startswith(T, i)
for _ in range(Q):
L, R = map(int, input().split())
print("Yes" if L - 1 <= R - M and acc[R - M + 1] > acc[L - 1] else "No")

acc[i] は、TT の出現のうち開始位置(0 始まり)が ii 未満のものの個数です。0 始まりで開始位置が L−1L - 1 以上 R−∣T∣R - |T| 以下の出現があるかを、acc[R - M + 1] > acc[L - 1] で調べています。R−L+1<∣T∣R - L + 1 < |T| のときは区間が空なので、先に L - 1 <= R - M で除いています。

Uiua
⋅◌⍥◡(&p⨬"No""Yes">0/-⬚0⊏-:⊜⋕⊸≠@ &sc):⊙:[2⧻]⟜(\+⌕)&sc&sc⋕&sc

⋕&sc で QQ、続く 2 つの &sc で SS と TT を読みます。

⟜(\+⌕) では、⌕ で SS の各位置から TT が始まるかの 0/1 の列を作り、\+ で累積和 PP にします。PkP_k は開始位置(0 始まり)が kk 以下の出現の個数です。⟜ で TT を残しておき、[2⧻] で [2,∣T∣][2, |T|] を作ります。:⊙: で並べ替えて、QQ の下に [2,∣T∣][2, |T|] と PP が来るようにしています。

⍥◡(…) で、[2,∣T∣][2, |T|] と PP を残したまま中の処理を QQ 回繰り返します。中の処理は次のとおりです。

  1. ⊜⋕⊸≠@ &sc でクエリを読んで [L,R][L, R] にします。
  2. -: で [L,R]−[2,∣T∣]=[L−2,R−∣T∣][L, R] - [2, |T|] = [L - 2, R - |T|] を計算します。
  3. ⬚0⊏ で PP からこの 2 か所を取り出し、/- で PR−∣T∣−PL−2P_{R - |T|} - P_{L - 2} を求めます。これが区間内にある開始位置の個数です。L=1L = 1 のときの添字 −1-1 は、⬚0 で 00 として扱っています。
  4. >0 で 11 個以上あるかを判定し、⨬"No""Yes" で文字列を選んで &p で出力します。

最後の ⋅◌ で、残しておいた [2,∣T∣][2, |T|] と PP を捨てています。

ABC478 C - Sort Subarray

長さ NN の整数列 AA の、長さ KK の連続部分列をちょうど 1 回だけ選んで昇順にソートします。その結果 AA 全体を昇順にできるかを判定する問題です(1≤K<N≤2×1051 \le K < N \le 2 \times 10^5)。

AA を昇順にソートした列を SS とします。区間 [i,i+K)[i, i + K) をソートして AA 全体が SS になるのは

  • 区間より前が SS と一致している(Aj=SjA_j = S_j, j<ij < i)
  • 区間より後ろが SS と一致している(Aj=SjA_j = S_j, j≥i+Kj \ge i + K)

のときです。このとき、区間の中の値の集まりも SS の対応する部分と一致するので、区間をソートすれば SS になります。逆に、区間の外は操作で変わらないので、この 2 つは必要です。

そこで

  • LiL_i = 先頭から ii 個がすべて SS と一致しているか
  • RiR_i = 位置 ii 以降がすべて SS と一致しているか

を前と後ろから求めておき、LiL_i かつ Ri+KR_{i+K} となる ii があるかを調べます。計算量はソートの O(Nlog⁡N)O(N \log N) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = sorted(A)
l = [True]
for i in range(N):
l.append(l[-1] and A[i] == s[i])
r = [True]
for i in reversed(range(N)):
r.append(r[-1] and A[i] == s[i])
r.reverse()
if any(l[i] and r[i + K] for i in range(N - K + 1)):
print("Yes")
else:
print("No")
Uiua
&p⨬"Yes""No">⊣:/+>0×⍜⇌\+⟜\+≠⍆.∩(⊜⋕⊸≠@ &sc)

≠⍆. で AA とソートした列を比べ、ずれている位置を 11 にした列を作ります。⟜\+ で前からの累積和、⍜⇌\+ で後ろからの累積和を取って × で掛けると、「前にも後ろにもずれがある位置」、つまりずれている最初の位置から最後の位置までが正になります。/+>0 でその長さを数え、⊣ で取り出した KK と > で比べて、KK を超えていれば "No"、そうでなければ "Yes" を ⨬ で選んで出力しています。

Blitz Round #25 C - Root Value

正の整数 xx に対して、xm\sqrt[m]{x} が自然数になるような最大の mm を f(x)f(x) とします。

長さ nn の数列 a1,…,ana_1, \ldots, a_n (2≤ai≤2002 \le a_i \le 200) と qq 個のクエリ (l,r)(l, r) が与えられるので、各クエリについて

f(∏i=lrai)f\left(\prod_{i=l}^{r} a_i\right)

を求める問題です。

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5、テストケースの nn の総和と qq の総和はそれぞれ 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

xx を素因数分解して x=p1e1p2e2⋯pkekx = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} とすると、xm\sqrt[m]{x} が整数になるのは、すべての指数 eje_j が mm の倍数のときです。したがって

f(x)=gcd⁡(e1,e2,…,ek)f(x) = \gcd(e_1, e_2, \ldots, e_k)

です。ai≥2a_i \ge 2 なので、積は 22 以上になり、指数のどれかは正になります。

積をそのまま計算すると巨大になりますが、指数だけを見れば足し算になります。ai≤200a_i \le 200 なので、現れる素数は 200200 以下の 4646 個だけです。各素数について指数の累積和を持っておけば、区間 [l,r][l, r] での各素数の指数は差を取るだけで求まり、その gcd⁡\gcd が答えです。

aia_i の上限を AA (=200= 200)、AA 以下の素数の個数を π(A)\pi(A) (=46= 46) とすると、計算量は O((n+q) π(A))O((n + q)\,\pi(A)) です。

Python
from math import gcd
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
for _ in range(int(input())):
N, Q = map(int, input().split())
A = list(map(int, input().split()))
acc = [[0] * len(prime)]
for a in A:
t = acc[-1].copy()
for i, p in enumerate(prime):
while a % p == 0:
t[i] += 1
a //= p
acc.append(t)
for _ in range(Q):
l, r = map(int, input().split())
l -= 1
ans = 0
for i in range(len(prime)):
ans = gcd(ans, acc[r][i] - acc[l][i])
print(ans)

Blitz Round #25 B - Jump Trip Score

長さ nn の整数列 a1,…,ana_1, \ldots, a_n があり、位置 i=1i = 1 から出発して i=n+1i = n + 1 に着いたら終わりです。スコアは 00 から始まり、各位置で次のどちらかを行います。

  • aia_i をスコアに足して i+1i + 1 に進む
  • 正の整数 dd (i+d≤n+1i + d \le n + 1) を選んで i+di + d に跳ぶ(スコアは変わらない)

跳ぶ操作は高々 1 回まで使えるとき、最終スコアの最大値を求める問題です。

  • 1≤n≤4⋅1051 \le n \le 4 \cdot 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、テストケースの nn の総和は 4⋅1054 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

ii から i+di + d に跳ぶと、ai,…,ai+d−1a_i, \ldots, a_{i+d-1} を飛ばすことになります。跳ぶのは高々 1 回なので、得られるスコアは

(先頭からの連続部分の和)+(末尾までの連続部分の和)(\text{先頭からの連続部分の和}) + (\text{末尾までの連続部分の和})

で、間の 1 区間を飛ばした形になります(跳ばなければ全部の和)。

そこで

  • LkL_k = 長さ kk 以下の接頭辞の和の最大値(空も含むので 00 以上)
  • RkR_k = 位置 k+1k + 1 以降から始まる接尾辞の和の最大値(空も含む)

を累積和で求めておけば、答えは

max⁡0≤k≤n(Lk+Rk)\max_{0 \le k \le n} (L_k + R_k)

です。接頭辞と接尾辞が重ならないように、境目 kk を全通り試しています。計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int,input().split()))
dp0 = [0]
x = 0
for a in A:
x += a
dp0.append(max(x, dp0[-1]))
dp1 = [0]
x = 0
for a in reversed(A):
x += a
dp1.append(max(x, dp1[-1]))
dp1.reverse()
print(max(x+y for x,y in zip(dp0,dp1)))

dp0 が LL、dp1 が RR にあたります。