コンテンツにスキップ

ABC483 D - Glitchy Robot

サイト
AtCoder
コンテスト
ABC483
問題
D - Glitchy Robot
難易度
965

数直線上の座標 00 にいるロボットが、順に A1,A2,…,ANA_1, A_2, \dots, A_N だけ移動します。移動を始める前に、AA の要素を高々 11 つ選んで符号を反転できます。

ロボットが一度以上通る整数座標の個数の最大値を求める問題です(N≤2×105N \le 2 \times 10^5)。

通る座標は累積和の最小値から最大値まで

Section titled “通る座標は累積和の最小値から最大値まで”

移動後の座標は累積和です。初期位置も含めて

P0=0,Pi=∑j=1iAjP_0 = 0, \qquad P_i = \sum_{j=1}^{i} A_j

とします。ロボットは連続的に移動するので、通る整数座標は min⁡Pi\min P_i から max⁡Pi\max P_i までのすべてです。よって、個数は

max⁡Pi−min⁡Pi+1\max P_i - \min P_i + 1

となります。

符号を反転する位置を全探索します。ただし、毎回累積和を作り直すと O(N2)O(N^2) かかるので、累積和の最小値・最大値を求められるセグメント木を使います。

各区間に、区間の総和 ss、空の接頭辞も含めた累積和の最小値 ll、最大値 rr を持たせます。空の接頭辞の和は 00 なので、初期位置も考慮できます。

左の区間の情報を (sL,lL,rL)(s_L, l_L, r_L)、右の区間の情報を (sR,lR,rR)(s_R, l_R, r_R) とすると、つなげた区間の情報は

s=sL+sR,l=min⁡(lL,sL+lR),r=max⁡(rL,sL+rR)\begin{aligned} s &= s_L + s_R, \\ l &= \min(l_L, s_L + l_R), \\ r &= \max(r_L, s_L + r_R) \end{aligned}

です。右の区間の累積和には、左の区間の総和 sLs_L が加わることを使っています。

11 要素 aa の情報は (a,min⁡(0,a),max⁡(0,a))(a, \min(0,a), \max(0,a)) です。この情報をセグメント木で管理すると、AiA_i を −Ai-A_i に変える操作を 11 点更新で行えます。

最初に反転しない場合の答えを求めます。その後、各位置について「符号を反転する」「全体の最大値と最小値から答えを更新する」「元に戻す」を行います。

各位置の更新は O(log⁡N)O(\log N)、全体の情報の取得は O(1)O(1) なので、計算量は O(Nlog⁡N)O(N \log N) です。

C++
#include "shogo-library/algebra/monoid.hpp"
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N);
VL(A, N);
SegTree<monoid::PrefixSumMinMax<ll>> seg(A);
ll ans = seg.all_prod().max - seg.all_prod().min + 1;
rep(i, N) {
seg.set(i, -A[i]);
chmax(ans, seg.all_prod().max - seg.all_prod().min + 1);
seg.set(i, A[i]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

実装では、自作ライブラリの PrefixSumMinMax と SegTree を使っています。all_prod() の min と max が、初期位置 00 を含む累積和の最小値・最大値です。