AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

题意翻译

你和对手都只有两种出拳方式:石头($g$)和布($p$),规则一样,赢了得一分,平局不得分,输了减一分。 现给你对手的出拳方式,设你到 $i$ 位置共出了 $x_i$ 次石头,$y_i$ 次布,在对于任意位置 $i$ 满足 $x_i \geq y_i$ 的条件下,输出你能得到的最大分数。

题目描述

[problemUrl]: https://abc046.contest.atcoder.jp/tasks/arc062_b シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。 このゲームは $ N $ ターンからなります。各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。ただし、各プレイヤーは次の条件を満たす必要があります。 (※) 各ターンの後で、(今までにパーを出した回数) $ ≦ $ (今までにグーを出した回数) を満たす このゲームでの各プレイヤーの得点は、(勝ったターンの数) $ - $ (負けたターンの数) です。 AtCoDeerくんは特殊能力を持っているので、ゲームが始まる前にTopCoDeerくんの出す $ N $ ターンの手を全て知ることが出来ました。 AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。 TopCoDeerくんの出す手の情報は文字列 $ s $ で与えられます。 $ s $ の $ i(1≦i≦N) $ 文字目が `g`のときは $ i $ ターン目でTopCoDeerくんがグーを出すことを、 `p`のときはパーを出すことを表します。

输入输出格式

输入格式


The input is given from Standard Input in the following format: ``` $ s $ ```

输出格式


Print the AtCoDeer's maximum possible score.

输入输出样例

输入样例 #1

ggppgggpgg

输出样例 #1

2

输入样例 #2

ggppgggpgg

输出样例 #2

2

说明

### 制約 - $ 1≦N≦10^5 $ - $ N=|s| $ - $ s $ の各文字は`g`か`p` - $ s $ で表される手は、条件(※)を満たしている ### Problem Statement AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of $ N $ turns. In each turn, each player plays one of the two _gestures_, _Rock_ and _Paper_, as in Rock-paper-scissors, under the following condition: (※) After each turn, (the number of times the player has played Paper) $ ≦ $ (the number of times the player has played Rock). Each player's score is calculated by (the number of turns where the player wins) $ - $ (the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors. _(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)_ With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the $ N $ turns, before the game starts. Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score. The gesture that TopCoDeer will play in each turn is given by a string $ s $ . If the $ i $ -th $ (1≦i≦N) $ character in $ s $ is `g`, TopCoDeer will play Rock in the $ i $ -th turn. Similarly, if the $ i $ -th $ (1≦i≦N) $ character of $ s $ in `p`, TopCoDeer will play Paper in the $ i $ -th turn. ### Constraints - $ 1≦N≦10^5 $ - $ N=|s| $ - Each character in $ s $ is `g` or `p`. - The gestures represented by $ s $ satisfy the condition (※). ### Sample Explanation 1 常に相手とあいこになるように手を出すことで、 $ 0 $ 点を取ることができて、これが最大値です。 ### Sample Explanation 2 例えばグー,パー,グー,パー,グー,グー,パー,パー,グー,パー と出すことで、 $ 3 $ 回勝って $ 1 $ 回負けているので得点は $ 2 $ 点になり、これが最大値です。 ### Sample Explanation 3 Playing the same gesture as the opponent in each turn results in the score of $ 0 $ , which is the maximum possible score. ### Sample Explanation 4 For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of $ 2 $ , which is the maximum possible score.