ABC 27 D - ロボット ( Adhoc )

D: ロボット - AtCoder Beginner Contest 027 | AtCoder
各Mについて右、左のどちらにすすむかをいちいち決めるとやばい。そもそもそれを早くする方法もあまり考えられない。しかしよく考えると、右に移動と決めたら、移動しないと比べて全体的に 右にある +の数 - 右にある -の数 の分スコアが増える。左に移動する事も同じように、右に移動するのと正負反対のスコアが得られる。問題の制限により、右に移動する数は最終的に左に移動する数と等しくならなければいけないので、つまりこの增減を計算してソートして半分ずつ、最終スコアが最大なるよう分ければいい。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;

string s;

void solve(){
    vector<int> cont; // contribution
    int pcnt = 0, ncnt = 0; // positive / negative sign count
    for(int i = s.size() - 1; i >= 0; --i){
        if( s[ i ] == 'M' )
            cont.push_back( pcnt - ncnt );
        else if( s[ i ] == '+' )
            ++pcnt;
        else
            ++ncnt;
    }
    sort( cont.begin(), cont.end() );
    int ans = 0;
    for(int i = 0; i < cont.size() / 2; ++i)
        ans += -cont[ i ];
    for(int i = cont.size() / 2; i < cont.size(); ++i)
        ans += cont[ i ];
    cout << ans << endl;
}

int main(){
    cin >> s;
    solve();
    return 0;
}