mayoko’s diary

プロコンとかいろいろ。

AtCoder Beginner Contest 027 D - ロボット

ぐぬぬ

解法

スライドがわかりやすいのでほとんどそのままです。

www.slideshare.net

一応すこし補足すると,最終的な答えがソートした際の(後半そのまま) - (前半そのまま) で良いのは, 後半を + 方向に進むのに,前半を - 方向に進むのに割り当てているからですね。

string s;
int N = 0;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    N = s.size();
    vector<int> plus;
    int cur = 0;
    for (int i = N-1; i >= 0; i--) {
        if (s[i] == '+') cur++;
        else if (s[i] == '-') cur--;
        else plus.push_back(cur);
    }
    sort(plus.begin(), plus.end());
    int ans = 0;
    int M = plus.size();
    for (int i = 0; i < M/2; i++) ans -= plus[i];
    for (int i = 0; i < M/2; i++) ans += plus[i+M/2];
    cout << ans << endl;
    return 0;
}