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

No.161 制限ジャンケン

■■■問題■■■

yuki君は友人と制限ジャンケンで遊ぶことにした。

この制限ジャンケンでは、全部でN回のジャンケンを行う(あいこも1回に数える)。
yuki君はN回のうち、グーをG回、チョキをC回、パーをP回しか出すことができない。

yuki君は1回ジャンケンで勝利すると3ポイント、あいこだと1ポイントを得る。負けるとポイントの増減はない。
幸い、yuki君は超能力で友人の手を事前にすべて読むことができた。
yuki君が最適手を取った場合、N回のジャンケンで得られるyuki君の合計取得ポイントの最大値を求めよ。

■■■入力■■■

G C P
S

G,C,Pはそれぞれyuki君が出せるグー・チョキ・パーの回数を示す整数である。
Sは相手の手を示す文字列であり、'G','C','P'のみで構成される。
Sのi文字目が'G','C','P'である場合、
相手のi回目のジャンケンの手はそれぞれグー・チョキ・パーであることを示す。

入力は1 <= |S| <= 300かつ|S|=G+C+Pを満たす。
yuki君と友人の出すグー・チョキ・パーの数は一致するとは限らない点に注意せよ。

■■■出力■■■

yuki君が得られるポイントの最大値を1行で答えよ。


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input5";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2 1 1");
            WillReturn.Add("CCGP");
            //12
            //グー・グー・パー・チョキの順で出せば四戦全勝である
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 0 5");
            WillReturn.Add("CCCCC");
            //0
            //なすすべもなく全敗してしまった
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7 6 5");
            WillReturn.Add("GCPGPCPGGGPCCCGPGP");
            //50
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int CardCntG = wkArr[0];
        int CardCntC = wkArr[1];
        int CardCntP = wkArr[2];

        char[] SArr = InputList[1].ToCharArray();
        int AiteCntG = SArr.Count(X => X == 'G');
        int AiteCntC = SArr.Count(X => X == 'C');
        int AiteCntP = SArr.Count(X => X == 'P');

        int Score = 0;

        //勝てるカードを全て割当
        Score += ExecWariate(ref CardCntG, ref AiteCntC) * 3;
        Score += ExecWariate(ref CardCntC, ref AiteCntP) * 3;
        Score += ExecWariate(ref CardCntP, ref AiteCntG) * 3;

        //あいこになるカードを全て割当
        Score += ExecWariate(ref CardCntG, ref AiteCntG);
        Score += ExecWariate(ref CardCntC, ref AiteCntC);
        Score += ExecWariate(ref CardCntP, ref AiteCntP);

        Console.WriteLine(Score);
    }

    //貪欲法で、カードを割当し、割当枚数を返す
    static int ExecWariate(ref int pCardCnt, ref int pAiteCnt)
    {
        int WillReturn;
        //全て割当可能の場合
        if (pCardCnt <= pAiteCnt) {
            WillReturn = pCardCnt;
            pAiteCnt -= pCardCnt;
            pCardCnt = 0;
            return WillReturn;
        }
        //一部割当可能の場合
        WillReturn = pAiteCnt;
        pCardCnt -= pAiteCnt;
        pAiteCnt = 0;
        return WillReturn;
    }
}


解説

貪欲法のアルゴリズムを使ってます。
最強最速アルゴリズマー養成講座: そのアルゴリズム、貪欲につき