トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ABC-046-D AtCoDeerくんと変なじゃんけん

■■■問題■■■

シカのAtCoDeerくんは友達のTopCoDeerくんとあるゲームをして対戦しています。
このゲームはNターンからなります。
各ターンではそれぞれのプレイヤーはじゃんけんのグーかパーを出します。
ただし、各プレイヤーは次の条件を満たす必要があります。

(※) 各ターンの後で、(今までにパーを出した回数) <= (今までにグーを出した回数)を満たす

このゲームでの各プレイヤーの得点は、(勝ったターンの数) - (負けたターンの数) です。
AtCoDeerくんは特殊能力を持っているので、
ゲームが始まる前にTopCoDeerくんの出すNターンの手を全て知ることが出来ました。

AtCoDeerくんの各ターンでの手を決めて、AtCoDeerくんの得点を最大化してください。
TopCoDeerくんの出す手の情報は文字列sで与えられます。
sの i(1 <= i <= N) 文字目がgのときはiターン目でTopCoDeerくんがグーを出すことを、
pのときはパーを出すことを表します。

■■■入力■■■

s

●1 <= N <= 10万
●N=|s|
●sの各文字はgかp
●sで表される手は、条件(※)を満たしている

■■■出力■■■

AtCoDeerくんの得点の最大値を出力せよ。


C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("gpg");
            //0
            //常に相手とあいこになるように手を出すことで、
            //0点を取ることができて、これが最大値です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("ggppgggpgg");
            //2
            //例えばグー,パー,グー,パー,グー,グー,パー,パー,グー,パーと出すことで、
            //3回勝って1回負けているので得点は2点になり、これが最大値です。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string s = InputList[0];

        int Score=0;
        for (int I = 0; I <= s.Length - 1; I++) {
            //自分がグーで相手がパー
            if (I % 2 == 0 && s[I] == 'p') Score--;

            //自分がパーで相手がグー
            if (I % 2 == 1 && s[I] == 'g') Score++;
        }
        Console.WriteLine(Score);
    }
}


解説

相手がグーの場合 自分がグーを出すと0点
                 自分がパーを出すと1点

相手がパーの場合 自分がグーを出すと-1点
                 自分がパーを出すと 0点

∴ (グーを出した時の得点+1) = (パーを出した時の得点) が成立します。
∴ 相手の手に関係なく、可能な限りパーを出すのが最適となります。