ARC-038-A カードと兄妹

■■■問題■■■

N枚のカードがあり、i(1 <= i <= N) 枚目のカードには整数Aiが書かれています。
ゲーム好きの兄妹はこれらのカードを使ってゲームをしようとしています。

●最初に全てのカードを、カードに書かれた整数が見えるようにテーブルの上に並べる。
●プレイヤーは自分のターンに、テーブルの上にあるカードからちょうど1枚のカードを選んで取る。
●テーブルの上にカードがなくなるまで、交互にターンを繰り返す。
●最終的に、自分が取ったカードに書かれた整数の和がプレイヤーのスコアとなる。

2人ともが自分のスコアを出来るだけ大きくしようとしたとき、先手のスコアはいくつになるでしょうか？

■■■入力■■■

N
A1 A2 ・・・ AN

●1行目には、カードの枚数を表す整数 N(1 <= N <= 1000) が与えられる。
●2行目には、各カードに書かれた整数を表すN個の整数が空白区切りで与えられる。
  このうち i(1 <= i <= N) 番目の整数 Ai(1 <= Ai <= 1000) は、i枚目のカードに書かれた整数を表す。

■■■出力■■■

先手のスコアを1行に出力せよ。出力の末尾に改行を入れること。

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("2");
            WillReturn.Add("400 628");
            //628
            //この例では、ゲームは以下のように進行します。
            //●先手が2枚目のカードを取る。
            //●後手が1枚目のカードを取る。
            //このとき、先手のスコアは628となり、後手のスコアは400となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("2 5 9 6 5");
            //16
            //この例では、ゲームは以下のように進行します。
            //●先手が3枚目のカードを取る。
            //●後手が4枚目のカードを取る。
            //●先手が2枚目のカードを取る。
            //●後手が5枚目のカードを取る。
            //●先手が1枚目のカードを取る。
            //このとき、先手のスコアは16となり、後手のスコアは11となります。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        Array.Sort(NArr, (A, B) => B.CompareTo(A));

        int Answer = 0;
        for (int I = 0; I <= NArr.GetUpperBound(0); I += 2) {
            Answer += NArr[I];
        }
        Console.WriteLine(Answer);
    }
}

解説

ナイーブにシュミレーションしてます。