【AtCoder】ABC 483 D - Glitchy Robot

D - Glitchy Robotatcoder.jp favicon

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 965 / NoviSteps: 1Q / 配点: 400 点

問題概要

数直線上にロボットがいて、はじめ、ロボットは座標 00 にある。

また、高橋君は長さ NN の整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) を持っていて、次の操作を行う。

  • AA の要素を高々 11 つ選び、その符号を反転させる。
  • ロボットを起動する。ロボットは起動後、NN 回の行動を行う。ii 回目の行動では、現在の座標を xx として、座標 x+Aix+A_i へ直線的に移動する。

高橋君はロボットが一度以上通る整数座標の個数をなるべく多くしたい。 高橋君が最適に行動したときの、「ロボットが一度以上通る整数座標の個数」としてあり得る最大の値を求めよ。

制約

  • 1≤N≤2×1051 \leq N \leq 2\times 10^5
  • −109≤Ai≤109-10^9 \leq A_i \leq 10^9
  • Ai≠0A_i\neq 0
  • 入力はすべて整数

考察

ロボットが移動中に到達する座標の最小値を LL、最大値を RR とすると、通過した整数座標の個数は R−L+1R - L + 1 で求められる。

したがって、各 AiA_i の符号を反転したときの最小座標・最大座標を効率的に求めればよい。


まず、配列 AA の累積和を

S0=0,Si=∑j=1iAjS_0=0, \quad S_i=\sum_{j=1}^{i}A_j

と定義する。

ここで、ある AiA_i の符号を反転させたときを考えると、

Sj′={Sj(j<i)Sj−2Ai(j≥i)S'_j= \begin{cases} S_j & (j < i) \\ S_j-2A_i & (j \geq i) \end{cases}

となる。 つまり、符号を反転させた位置以降の累積座標が、すべて −2Ai-2A_i だけ平行移動するのである。

AiA_i の符号を反転させたときのロボットの最小座標を LiL_i とすると、

Li=min⁡(S0′,S1′,…,SN′)L_i = \min(S'_0,S'_1,\ldots,S'_N)

と書ける。

ii を境に前半と後半に分けて考えると、次のようになる。

Li:0≤j<iL_i: 0 \leq j < i のとき

この区間では Sj′=SjS'_j=S_j なので、

min⁡0≤j<iSj′=min⁡0≤j<iSj\underset{0\leq j < i}{\min}S'_j = \underset{0 \leq j < i}{\min}S_j

であり、これは前からの累積min pre_mii−1\mathrm{pre\_mi}_{i-1} に一致する。

Li:i≤j≤NL_i: i \leq j \leq N のとき

この区間では Sj′=Sj−2AiS'_j = S_j-2A_i なので、

min⁡i≤j≤NSj′=min⁡i≤j≤N(Sj−2Ai)=(min⁡i≤j≤NSj)−2Ai\begin{aligned} \underset{i \leq j \leq N}{\min}S'_j &= \underset{i \leq j \leq N}{\min}(S_j-2A_i) \\ &= \left( \underset{i \leq j \leq N}{\min}S_j \right) - 2A_i \\ \end{aligned}

であり、右辺第1項の min⁡i≤j≤NSj\underset{i \leq j \leq N}{\min}S_j は後ろからの累積min suf_mii\mathrm{suf\_mi}_i に一致する。


全体の最小値は前述の2つの区間の最小値のうち小さい方になるので、次の式が成り立つ。

Li=min⁡(pre_mii−1,suf_mii−2Ai)L_i=\min \left( \mathrm{pre\_mi}_{i-1}, \mathrm{suf\_mi}_i - 2A_i \right)

最大座標 RiR_i についても、前後の累積max pre_mxi−1\mathrm{pre\_mx}_{i-1}, suf_mxi\mathrm{suf\_mx}_i を用いて同様に求めることができる。

Ri=max⁡(pre_mxi−1,suf_mxi−2Ai)R_i=\max \left( \mathrm{pre\_mx}_{i-1}, \mathrm{suf\_mx}_i - 2A_i \right)

あとは、i=1,2,…,Ni = 1,2,\ldots,N について、Ri−Li+1R_i - L_i + 1 の最大値を求めればよい。

なお、AiA_i の符号を反転させない場合は、L0=pre_miNL_0=\mathrm{pre\_mi}_N、R0=pre_mxNR_0=\mathrm{pre\_mx}_N で求めることができる。


計算量は、前計算で累積和や累積min/maxを求める部分がボトルネックとなり、O(N)O(N) である。

実装例

CPP
1.#include <bits/stdc++.h>
2.using namespace std;
3.
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)
6.
7.constexpr long long INFL = 1e+18;
8.
9.using ll = long long;
10.
11.template <typename T>
12.inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
13.
14.// ======================================== //
15.
16.int main()
17.{
18. int N;
19. cin >> N;
20. vector<ll> A(N);
21. rep(i, 0, N) cin >> A[i];
22.
23. vector<ll> ps(N + 1, 0);
24. rep(i, 0, N) ps[i + 1] = ps[i] + A[i];
25.
26. vector<ll> pre_mi(N + 1, INFL), pre_mx(N + 1, -INFL);
27. pre_mi[0] = pre_mx[0] = 0;
28. rep(i, 0, N) {
29. pre_mi[i + 1] = min(pre_mi[i], ps[i + 1]);
30. pre_mx[i + 1] = max(pre_mx[i], ps[i + 1]);
31. }
32.
33. vector<ll> suf_mi(N + 1, INFL), suf_mx(N + 1, -INFL);
34. suf_mi[N] = suf_mx[N] = ps[N];
35. rrep(i, N - 1, 0) {
36. suf_mi[i] = min(suf_mi[i + 1], ps[i]);
37. suf_mx[i] = max(suf_mx[i + 1], ps[i]);
38. }
39.
40. ll ans = pre_mx[N] - pre_mi[N] + 1;
41. rep(i, 1, N + 1) {
42. ll l = min(pre_mi[i - 1], suf_mi[i] - 2 * A[i - 1]);
43. ll r = max(pre_mx[i - 1], suf_mx[i] - 2 * A[i - 1]);
44. chmax(ans, r - l + 1);
45. }
46.
47. cout << ans << endl;
48.
49. return 0;
50.}
atcoder.jp favicon

実装時間: 30分

コメント

反転操作を行わない場合も考慮する必要があることに注意する。