ARC066 E - Addition and Subtraction Hard -

問題

解説

公式
https://atcoder.jp/img/arc066/editorial.pdf
kmjpさん
AtCoder ARC #066 : E - Addition and Subtraction Hard - kmjp's blog

考察

どうすれば式の値を最大化できるかを考える。

-の後に開き括弧を挿入して、引く値をできるだけ小さくできたら良さそう。
また、+の後に開き括弧を挿入しても意味はない。(式の値を増やすことはできない)

上記の考察から-の後に括弧を挿入することだけ考えればいい。また全ての-の後に開き括弧を挿入してもいいことも分かる。（開き括弧を挿入する必要がなかった場合でもその後の数の直後で閉じればいいため）

すると
dp[i][j] = i 項目の直後で、j 個括弧が開いている時の、そこまでの式の値の最大値というような DP を思いつく。

しかし、これは O(N²) なのでまずい。
iは減らせなそうなので、jをどうにか減らしたい。

考察をすると、開き括弧を挿入した後の式の値は符号が反転すると考えられることが分かる。
- A - B - C - Dで表される式があったとして、
- A -(B - C - D) 　…(i)
- A -(B -(C -(D))) …(ii)
の２つの括弧挿入後の式を考える。
Dの部分に着目すると
(i)のDはB前の-(によって式の値の符号が反転している。
(ii)のDはD前の-(によって反転、C前の-(によって反転、B前の-(によって反転、計３回反転している。
符号が１回反転しているのと３回反転しているのは実質やっていることは変わらない（式の値は変わらない）ので同じものと考えていよいことが分かる。

上記の考察から括弧を開くのは高々２回でよいことが分かる。(偶奇だけ考えればよいため)

よって j の範囲は 0∼2 だけを考えればよくなり、この DP が O(N) でできることが分かった。

ソースコード

signed main() {
    int N;
    int A[100001];
    char op[100001];
    int dp[100001][3];   
 
    fill_n(*dp, 100001*3, -INF);
    
    cin >> N;
    cin >> A[0];
    dp[0][0] = A[0];
 
    for ( int i = 1; i < N; i++ ) cin >> op[i] >> A[i];
    
    for ( int i = 1; i < N; i++ ) {
        if ( op[i] == '+' ) {
            dp[i][0] = dp[i-1][0]+A[i];
            dp[i][1] = dp[i-1][1]-A[i];
            dp[i][2] = dp[i-1][2]+A[i];
        } else {
            //open
            dp[i][1] = max(dp[i-1][0], dp[i-1][2])-A[i];
            dp[i][0] = dp[i][2] = dp[i-1][1]+A[i];          
        }
 
        //close
        dp[i][1] = max(dp[i][1], dp[i][2]);
        dp[i][0] = max(dp[i][0], dp[i][1]);
    }
 
    cout << *max_element(dp[N-1], dp[N-1]+3) << endl;
 
    return 0;
}

感想

コードはとても短いけど、解法を理解するのに結構時間がかかった。