E - Good Partition Editorial by MMNMM
別解空間計算量が \(O(1)\) である解法を紹介します。
導出
スコアの総和 \(\sum _ iS(B _ i)\) を \(\sum _ ix _ iA _ i\) の形に書き下すと
- \(x _ i\in\lbrace-1,0,1\rbrace\)
- \(\displaystyle-1\leq\sum _ {i=1} ^ kx _ i\leq 1\ (1\leq k\lt N)\)
- \(\displaystyle\sum _ {i=1} ^ Nx _ i=0\)
が成り立ちます。
逆に、この条件を満たすような \((x _ i)\) に対して、 適切に \(B _ i\) を選ぶことで \(\sum _ ix _ iA _ i\) に対して \(\sum _ ix _ iA _ i\leq\sum _ iS(B _ i)\) であるようにできることを示します。
\(\displaystyle\sum _ {i=1} ^ kx _ i=0\) なる \(k\ (0\leq k\leq N)\) を \(k _ 0,k _ 1,\ldots,k _ K\) とします。 条件より、\(k _ 0=0,k _ K=N\) です。
\(B _ i\) を \((A _ {k _ {i-1}+1},A _ {k _ {i-1}+2},\ldots,A _ {k _ i})\) とすると、\(\displaystyle\sum _ {j=k _ {i-1}+1} ^ {k _ i}x _ jA _ j\) は \(0\) もしくは \(A _ {k _ {i-1}+1}-A _ {k _ i}\) もしくは \(A _ {k _ i}-A _ {k _ {i-1}+1}\) です。
よって、 \[\begin{aligned} \sum _ {j=k _ {i-1}+1} ^ {k _ i}x _ jA _ j&\leq\max\lbrace A _ {k _ {i-1}+1},A _ {k _ i}\rbrace-\min\lbrace A _ {k _ {i-1}+1},A _ {k _ i}\rbrace\\ &\leq\max _ {k _ {i-1}+1\leq j\leq k _ i}\lbrace A _ j\rbrace-\min _ {k _ {i-1}+1\leq j\leq k _ i}\lbrace A _ j\rbrace\\ &=S(B _ i) \end{aligned}\] となります。
ここから、\(\sum _ ix _ iA _ i\leq\sum _ iS(B _ i)\) が示されました。
よって、\(\sum _ ix _ iA _ i\) の最大値は \(\sum _ iS(B _ i)\) の最大値と等しいです。
以上より、条件
- \(x _ i\in\lbrace-1,0,1\rbrace\)
- \(\displaystyle-1\leq\sum _ {i=1} ^ kx _ i\leq 1\ (1\leq k\lt N)\)
- \(\displaystyle\sum _ {i=1} ^ Nx _ i=0\)
をみたす整数列 \((x _ 1,x _ 2\ldots,x _ N)\) 全体の集合を \(X\) として \[\max _ {(x _ 1,\ldots,x _ N)\in X}\sum _ iA _ ix _ i\] が求める答えです。
\(A\) を先頭から走査しつつ、現在の \(\sum _ ix _ i\) の値に対応する \(3\) 状態をもつことでこれを求めることができます。
実装例は以下のようになります。
#include <iostream>
#include <tuple>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
long inf = 1e10;
tuple<long, long, long> state = {-inf, 0, -inf}; // ∑ x_i がそれぞれ (-1, 0, 1) の状態
auto&&[negative, zero, positive] = state;
for (int i = 0; i < N; ++i) {
int a;
cin >> a;
state = {max(negative, zero - a),
max({negative + a, zero, positive - a}),
max(zero + a, positive)};
}
cout << zero << endl;
return 0;
}
posted:
last update: