DPコンテスト
次のDPコンテストの問題へ
前のDPコンテストの問題へ
TDP B ゲーム
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("1 2");
WillReturn.Add("1");
WillReturn.Add("2 10");
//11
}
else if (InputPattern == "Input2") {
WillReturn.Add("5 5");
WillReturn.Add("2 4 5 4 2");
WillReturn.Add("2 8 3 4 5");
//21
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int[] mAArr;
static int[] mBArr;
static int UB_A;
static int UB_B;
static void Main()
{
List<string> InputList = GetInputList();
mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
mBArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();
UB_A = mAArr.GetUpperBound(0);
UB_B = mBArr.GetUpperBound(0);
int Result = DFS(0, 0);
// 加減法で連立方程式を解く
int SumVal = mAArr.Sum() + mBArr.Sum();
int Answer = (Result + SumVal) / 2;
Console.WriteLine(Answer);
}
static Dictionary<int, int> mMemoDict = new Dictionary<int, int>();
static int DFS(int pAInd, int pBInd)
{
int Hash = pAInd * 10000 + pBInd;
if (mMemoDict.ContainsKey(Hash)) {
return mMemoDict[Hash];
}
// 先手番か後手番かを求める
int IndSum = pAInd + pBInd;
bool IsSente = IndSum % 2 == 0;
var SeniList = new List<int>();
if (pAInd <= UB_A) {
int Result = DFS(pAInd + 1, pBInd);
if (IsSente) Result += mAArr[pAInd];
else Result -= mAArr[pAInd];
SeniList.Add(Result);
}
if (pBInd <= UB_B) {
int Result = DFS(pAInd, pBInd + 1);
if (IsSente) Result += mBArr[pBInd];
else Result -= mBArr[pBInd];
SeniList.Add(Result);
}
if (SeniList.Count > 0) {
if (IsSente) return mMemoDict[Hash] = SeniList.Max();
return mMemoDict[Hash] = SeniList.Min();
}
return mMemoDict[Hash] = 0;
}
}
解説
先手と後手の得点の総合計は決まってます。
先手の得点 - 後手の得点 をSとおいて
先手はSを最大化しようとして
後手はSを最小化しようとします。
後は、メモ化再帰で
先手は遷移可能な状態からSが最大の状態を選び
後手は遷移可能な状態からSが最小の状態を選ぶ
ようにします。
先手の合計 + 後手の合計 は、最初から分かるので
先手の合計 - 後手の合計 をメモ化再帰で求めれば、後は、
加減法で連立方程式を解いて、答えが分かります。
類題