ABC483 D - Glitchy Robot
- サイト
- AtCoder
- コンテスト
- ABC483
- 問題
- D - Glitchy Robot
- 難易度
- 965
数直線上の座標 にいるロボットが、順に だけ移動します。移動を始める前に、 の要素を高々 つ選んで符号を反転できます。
ロボットが一度以上通る整数座標の個数の最大値を求める問題です()。
通る座標は累積和の最小値から最大値まで
Section titled “通る座標は累積和の最小値から最大値まで”移動後の座標は累積和です。初期位置も含めて
とします。ロボットは連続的に移動するので、通る整数座標は から までのすべてです。よって、個数は
となります。
符号を反転する位置を全探索します。ただし、毎回累積和を作り直すと かかるので、累積和の最小値・最大値を求められるセグメント木を使います。
区間をつなげるための情報
Section titled “区間をつなげるための情報”各区間に、区間の総和 、空の接頭辞も含めた累積和の最小値 、最大値 を持たせます。空の接頭辞の和は なので、初期位置も考慮できます。
左の区間の情報を 、右の区間の情報を とすると、つなげた区間の情報は
です。右の区間の累積和には、左の区間の総和 が加わることを使っています。
要素 の情報は です。この情報をセグメント木で管理すると、 を に変える操作を 点更新で行えます。
最初に反転しない場合の答えを求めます。その後、各位置について「符号を反転する」「全体の最大値と最小値から答えを更新する」「元に戻す」を行います。
各位置の更新は 、全体の情報の取得は なので、計算量は です。
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 が、初期位置 を含む累積和の最小値・最大値です。