【AtCoder】ABC 483 D - Glitchy Robot

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 965 / NoviSteps: 1Q / 配点: 400 点
問題概要
数直線上にロボットがいて、はじめ、ロボットは座標 にある。
また、高橋君は長さ の整数列 を持っていて、次の操作を行う。
- の要素を高々 つ選び、その符号を反転させる。
- ロボットを起動する。ロボットは起動後、 回の行動を行う。 回目の行動では、現在の座標を として、座標 へ直線的に移動する。
高橋君はロボットが一度以上通る整数座標の個数をなるべく多くしたい。 高橋君が最適に行動したときの、「ロボットが一度以上通る整数座標の個数」としてあり得る最大の値を求めよ。
制約
- 入力はすべて整数
考察
ロボットが移動中に到達する座標の最小値を 、最大値を とすると、通過した整数座標の個数は で求められる。
したがって、各 の符号を反転したときの最小座標・最大座標を効率的に求めればよい。
まず、配列 の累積和を
と定義する。
ここで、ある の符号を反転させたときを考えると、
となる。 つまり、符号を反転させた位置以降の累積座標が、すべて だけ平行移動するのである。
の符号を反転させたときのロボットの最小座標を とすると、
と書ける。
を境に前半と後半に分けて考えると、次のようになる。
のとき
この区間では なので、
であり、これは前からの累積min に一致する。
のとき
この区間では なので、
であり、右辺第1項の は後ろからの累積min に一致する。
全体の最小値は前述の2つの区間の最小値のうち小さい方になるので、次の式が成り立つ。
最大座標 についても、前後の累積max , を用いて同様に求めることができる。
あとは、 について、 の最大値を求めればよい。
なお、 の符号を反転させない場合は、、 で求めることができる。
計算量は、前計算で累積和や累積min/maxを求める部分がボトルネックとなり、 である。
実装例
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.}実装時間: 30分
コメント
反転操作を行わない場合も考慮する必要があることに注意する。





