AtCoder Regular Contest 066 E - Addition and Subtraction Hard
過去問。
なんかやけにあっさり解けて、順位表見たら通してる人が意外と少なく、ついに僕も覚醒したか？ と思ったらXor Sum回だった
解法
正符号の後ろから括弧を開始するのは明らかに無意味です。ある負符号から何項かを括弧で括ることを考えます。（この括弧を外括弧と呼ぶことにします）
ここで、外括弧内の項はなるべく最終的に正にしてやりたいです。
このように負符号を区切りとして括るようにすると、与式において正符号が続く最初の何項かを除いて全部正にできることがわかります。
この最初の何項かというのは、外括弧の開始位置を固定して意味のある括り方をしようとすると必ず巻き込まれてしまいます。（必要な犠牲）
外括弧内の後ろの方は正にできるので、終了位置は与式の一番最後にするとよさそうです。外括弧は1つでよいこともわかります。
最終的に負となってしまうのは、開始位置からの何項かと、開始位置より前にあるもとから負だった項です。
ここまでわかれば、あとは与式を前から見ていって開始位置を動かしながら、なるべく大きくなるような答えを探せばよいです。
反省
正の項しかない場合の処理を忘れて1WA食らったものの、ほとんど解法に書いた道筋通りに考察を進め、スムーズに解くことができました。
コンテスト本番でもかくありたいものです。
