トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.161 制限ジャンケン
■■■問題■■■
yuki君は友人と制限ジャンケンで遊ぶことにした。
この制限ジャンケンでは、全部でN回のジャンケンを行う(あいこも１回に数える)。
yuki君はN回のうち、グーをG回、チョキをC回、パーをP回しか出すことができない。
yuki君は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君が得られるポイントの最大値を１行で答えよ。
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;
}
}
解説