ABC-031-C 数列ゲーム

■■■問題■■■

高橋君と青木君は長さNの数列Sを用いたゲームを行う。
ゲームは高橋君の手番と青木君の手番1回ずつからなる。

ゲームは以下の要領で行われる。
●最初に高橋君が数列の要素のうち1つに丸をつける。
●次に青木君が数列の要素で高橋君が丸を付けなかったもののうち1つに丸をつける。
●高橋君と青木君が丸を付けた2つの要素に対して、
  その2つの要素およびそれらの間にあるすべての要素を残して、
  それ以外の要素をすべて削除する。残った数列をTと置く。
●数列Tのうち、数列T内で左から奇数番目の要素の合計が高橋君の得点、
  偶数番目の要素の合計が青木君の得点となる。

青木君は、丸を付けられる要素の中で、青木君が得点を最も多く得られる要素に丸を付ける。
そのような要素が複数あるならばそれらのうち最も左側にある要素に丸を付ける。

高橋君は青木君の丸の付け方を知っている。高橋君が得られる得点として考えられる得点の最大値を求めよ。

■■■入力■■■

N
a1 a2 ・・・ aN

1行目には、整数N(2 <= N <= 50) が与えられる。Nは数列Sの要素数である。
2行目には、N個の整数 a1, a2, ・・・ , aN(-50 <= ai <= 50,1 <= i <= N) が与えられる。
整数aiは数列Sの左からi番目の要素を表す。

■■■出力■■■

高橋君が得られる得点の最大値を1行に出力せよ。
出力の末尾にも改行を入れること。

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("6");
            WillReturn.Add("1 -3 3 9 1 6");
            //6
            //高橋君は左から2番目の要素を選ぶのが最適である。
            //この場合、青木君は左から5番目の要素を選ぶことになり、
            //得られる数列Tは左から順に-3,3,9,1となる。
            //高橋君は6の得点を、青木君は4の得点を得ることができる。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("5 5 5");
            //10
            //青木君にとってどの要素を選んでも得られる得点が5であることには変わりがないが、
            //得られる得点が最大となる選び方が複数ある場合にその中で最も左を選ぶので、
            //高橋君の得点は10になりうる。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("8");
            WillReturn.Add("-1 10 -1 2 -1 10 -1 0");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();
        int UB = AArr.GetUpperBound(0);

        int TakahashiMax = int.MinValue;

        //高橋君の選択
        for (int I = 0; I <= UB; I++) {

            int wkTakahashiMax = int.MinValue;
            int AokiMax = int.MinValue;

            //青木君の選択
            for (int J = 0; J <= UB; J++) {
                if (I == J) continue;

                int Takahashi, Aoki;
                DeriveScore(AArr, out Takahashi, out Aoki, I, J);
                if (AokiMax < Aoki) {
                    AokiMax = Aoki;
                    wkTakahashiMax = Takahashi;
                }
            }

            if (TakahashiMax < wkTakahashiMax) {
                TakahashiMax = wkTakahashiMax;
            }
        }
        Console.WriteLine(TakahashiMax);
    }

    static void DeriveScore(int[] AArr, out int pTakahashi, out int pAoki, int pI, int pJ)
    {
        pTakahashi = pAoki = 0;

        int Cnt = 0;
        for (int LoopInd = Math.Min(pI, pJ); LoopInd <= Math.Max(pI, pJ); LoopInd++) {
            if (Cnt % 2 == 0) pTakahashi += AArr[LoopInd];
            if (Cnt % 2 == 1) pAoki += AArr[LoopInd];
            Cnt++;
        }
    }
}

解説

高橋君と青木君の全選び方を列挙しても 50*49通りしかないので、
全列挙してます。