C++ですべての操作後の石の山の最小数を求める方法

問題概要

n 文字の文字列 S が与えられます。各文字は '+' または '-' のいずれかです。ここに石の山があり、n 回にわたって「山から石を 1 個取り除く」か「山に石を 1 個追加する」という操作を行いました。ただし、石を取り除く操作の直前には、必ず山が空でない状態だったことが保証されています。i 番目の操作で石を取り除いた場合は S[i] = "-"、追加した場合は S[i] = "+" となります。

このとき、すべての操作を終えた後の石の山に残り得る石の数として考えられる最小値を求めてください。

たとえば、入力が S = "++-++" の場合、出力は 3 になります。最初に山に石が 0 個あったとすると、一連の操作をすべて行った後の石の数は 3 になります。

解法の手順

この問題を解くために、次の手順に従います。

n := S のサイズ
i := 0 で初期化し、i < n を満たす間、i を 1 ずつ増やしながら繰り返す:
    res := (S[i] が '-' ならば res - 1 と 0 の最大値、そうでなければ res + 1)
res を返す

アルゴリズムのポイント

石の数が負になることはあり得ないため、'-' の操作で res が 0 を下回る場合には 0 に丸めます（max(res - 1, 0)）。この処理により、山が空の状態で石を取り除こうとしたケースも正しく扱えます。文字列を先頭から一度走査するだけでよいため、計算量は O(n) と非常に効率的です。

C++ 実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
    int n = S.size(), res = 0;
    for (int i = 0; i < n; i++)
        res = (S[i] == '-') ? max(res - 1, 0) : res + 1;
    return res;
}
int main(){
    string S = "++-++";
    cout << solve(S) << endl;
}

入力

"++-++"

出力

3