[ABC046D] AtCoDeerくんと変なじゃんけん
题意翻译
你和对手都只有两种出拳方式:石头($g$)和布($p$),规则一样,赢了得一分,平局不得分,输了减一分。
现给你对手的出拳方式,设你到 $i$ 位置共出了 $x_i$ 次石头,$y_i$ 次布,在对于任意位置 $i$ 满足 $x_i \geq y_i$ 的条件下,输出你能得到的最大分数。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc046/tasks/arc062_b
シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。 このゲームは $ N $ ターンからなります。各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。ただし、各プレイヤーは次の条件を満たす必要があります。
(※) 各ターンの後で、(今までにパーを出した回数)$ ≦ $(今までにグーを出した回数) を満たす
このゲームでの各プレイヤーの得点は、(勝ったターンの数) $ - $ (負けたターンの数) です。 AtCoDeerくんは特殊能力を持っているので、ゲームが始まる前にTopCoDeerくんの出す $ N $ ターンの手を全て知ることが出来ました。 AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。 TopCoDeerくんの出す手の情報は文字列 $ s $ で与えられます。 $ s $ の $ i(1≦i≦N) $ 文字目が `g`のときは $ i $ ターン目でTopCoDeerくんがグーを出すことを、 `p`のときはパーを出すことを表します。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ s $
输出格式
AtCoDeerくんの得点の最大値を出力せよ。
输入输出样例
输入样例 #1
gpg
输出样例 #1
0
输入样例 #2
ggppgggpgg
输出样例 #2
2
说明
### 制約
- $ 1≦N≦10^5 $
- $ N=|s| $
- $ s $ の各文字は`g`か`p`
- $ s $ で表される手は、条件(※)を満たしている
### Sample Explanation 1
常に相手とあいこになるように手を出すことで、$ 0 $点を取ることができて、これが最大値です。
### Sample Explanation 2
例えばグー,パー,グー,パー,グー,グー,パー,パー,グー,パー と出すことで、 $ 3 $回勝って$ 1 $回負けているので得点は$ 2 $点になり、これが最大値です。