D - ロボット AtCoder Beginner Contest 027

D - ロボット
問題概略
M,+,-からなる命令文が与えられる。Mでは+か-の方に1移動でき、+なら現在地点、-なら-現在地点をポイントに加算する。
最終的に原点に戻っている必要がある場合、最高得点はなにか。

解法

1. される時変化する幸福量について考えてみる。

その値は現在地点であり、今までの> - <である。
今回+,-の位置は固定されており、最終的に>,<をいつ使うかが知りたいため、>,<について考える。
>を使うと最終的な答えが右にある+と-の差だけ増える。この変化量は現在何もしなかった場合との差であり右全部が反映されたものなので、他の><と独立して考えられる。
よって、あるタイミングでどこへ動くかによって、答えの変化量が一意に定まるため、原点に戻れるような動き方で最大の値が答えである。

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        char[] s = nca();
        N = s.length;
        int sum = 0;
        ArrayList<Integer> lis = new ArrayList<>();
        for (int i = N - 1; i >= 0; i--) {
            if (s[i] == 'M') {
                lis.add(sum);
            } else if (s[i] == '+') {
                sum++;
            } else {
                sum--;
            }
        }
        Collections.sort(lis);
        long res = 0;
        for (int i = 0; i < lis.size() / 2; i++) {
            res += lis.get(i) * -1;
        }
        Collections.sort(lis, Comparator.reverseOrder());

        for (int i = 0; i < lis.size() / 2; i++) {
            res += lis.get(i);
        }
        System.out.println(res);
    }