CODE FESTIVAL 2015予選A B とても長い数列

■■■問題■■■

高橋君は長さNの数列 A={A1,A2, ・・・ ,AN} を用意しました。
高橋君は数列Aを元に「とても長い数列」を、
以下のような手順で作ろうとしています。

●まず長さ0の数列を用意し、これをSと呼ぶことにする。
●S、A1、S をこの順につなげた数列を新たなSとする。
●S、A2、S をこの順につなげた数列を新たなSとする。
● (中略)
●S、AN、S をこの順につなげた数列を新たなSとする。
●この時点でのSを「とても長い数列」とする。

例えば N=3,A1=1,A2=2,A3=3 なら、S は {}　→ {1} → {1,2,1} → {1,2,1,3,1,2,1} と変化し、
「とても長い数列」は {1,2,1,3,1,2,1} となります。

高橋君はこの手順によって作られる「とても長い数列」に含まれる数の和を知りたがっています。
これを高橋君の代わりに計算するプログラムを作成してください。

■■■入力■■■

N
A1 A2 ... AN

●1行目には、整数 N(1 <= N <= 30) が与えられる。
●2行目には、N個の整数が空白区切りで与えられる。
  このうち i(1 <= i <= N) 番目には、整数 Ai(0 <= Ai <= 100) が与えられる。
●「とても長い数列」に含まれる数の和は 10の9乗以下となることが保証されている。

■■■出力■■■

「とても長い数列」に含まれる数の和を1行に出力せよ。出力の末尾に改行を入れること。

C#のソース

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

class Program
{
    static string InputPattern = "Input2";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 3");
            //11
            //この入力例は問題文中の例と同じです。
            //「とても長い数列」は {1,2,1,3,1,2,1} となり、
            //1+2+1+3+1+2+1=11 であるため11を出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8");
            WillReturn.Add("0 1 3 6 12 25 50 100");
            //652
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("30");
            WillReturn.Add("1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0");
            //536870912
            //「とても長い数列」はとても長くなることがあるので注意してください
        }
        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 N = AArr.Length;

        int SumVal = 0;
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            SumVal += AArr[I] * (int)Math.Pow(2, N - I - 1);
        }
        Console.WriteLine(SumVal);
    }
}

解説

数列を構成する整数が順に、1 2 3であれば

1+
1+2+1+
1+2+1+3+1+2+1
が解となります。

これは
 1*(2の3乗-1)
+2*(2の2乗-1)
+3*(2の1乗-1)
であることを使って計算してます。