ABC027 D問題 ロボット

M,+,-の3文字の列が与えられて、Mごとに数直線上のどちらかに移動し、+,-で点数を+,-していく。最後に原点に戻ってくる条件の元、最大の点数を考える問題。

dpは一瞬で思いついたけど、それじゃあ絶対len(S) == 1e5という制約は満たせないのは明らかだった。そこで考えるのは移動>,<の意味。>は結果的にMより右のプラスの数-マイナスの数分だけ点数を上昇させるということに気づけば、それをソートしてあげれば答えに辿り着く。この考察は逆転の発想ですごい面白いと思った。

    string S; cin >> S;
    vector<int> right;
    vector<int> left;
    int plus = 0, minus = 0;
    for(int i=len(S)-1; i>=0; i--){
        if(S[i] == '+'){
            plus++;
        }else if(S[i] == '-'){
            minus++;
        }else{
            right.push_back(plus-minus);
            left.push_back(minus-plus);
        }
    }
    sort(right.begin(), right.end());
    sort(left.begin(), left.end());
    int sum = 0;
    for(int i=0; i<len(right)/2; i++){
        sum += right[len(right)-1-i];
        sum += left[len(right)-1-i];
    }
    cout << sum << endl;