第2回 ドワンゴからの挑戦状 予選 B 積み鉛筆

■■■問題■■■

ニワンゴくんは鉛筆を積むのが好きです。
今日は以下の方法で鉛筆を積むことにしました。
まず、N本の鉛筆を左右に1列に床に並べます。左からi番目の鉛筆の長さはLiです。

次に、N-1本の鉛筆を、床に並べた隣り合う2つの鉛筆の間の上に積みます。
ただし、上に積む鉛筆の長さは、その下にある2つの鉛筆の長さのうち長い方と等しいです。
すなわち、上に積む鉛筆のうち、左からj番目のものの長さをKjと表すと、 
Kj=max{Lj,Lj+1}が成り立ちます。



例えば、上図のような鉛筆の積み方があります。
ここで、円の中に書かれている数は鉛筆の長さを表します。

積んだ鉛筆を上から見たとき、上に積まれたN-1本の鉛筆の長さのみ見え、
N本の土台にある鉛筆の長さは分かりません。
この状態で、土台となるN本の鉛筆の長さとしてありうるものを考えるゲームを
ニワンゴくんは思いつきました。

あなたの仕事はこのゲームに正解するプログラムを書くことです。
ただし、土台となる鉛筆の長さの組み合わせは存在することが保証されています。

すなわち、N-1個の数からなる数列{Kj}が与えられたとき、
Kj=max{Lj,Lj+1}(1 <= j <= N-1)がすべてのjについて成り立つような数列{Li}を求めてください。

■■■入力■■■

N
K1 K2 ・・・ KN-1

●1行目には、土台となる鉛筆の本数 N(2 <= N <= 10万)が与えられる。
●2行目には、上に積まれている鉛筆の長さを表すN-1個の整数K1,・・・,KN-1が空白区切りで与えられる。
●1 <= Ki <= 10億(1 <= i <= N)が成り立つ。

■■■出力■■■

土台となる鉛筆の長さL1,・・・,LNを空白区切りで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("4");
            WillReturn.Add("3 5 5");
            //1 3 5 4
            //1,3,5,4の長さの鉛筆を土台として3本の鉛筆を上に積むと、
            //積まれた鉛筆の長さはそれぞれ3,5,5となることが分かります。
            //よって、1,3,5,4は答えの条件を満たします。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("4 8 8 2 5");
            //4 4 8 2 2 5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("1 2 3 4");
            //1 1 2 3 4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //貪欲法で解く
        var AnswerList = new List<int>();
        AnswerList.Add(wkArr[0]);
        for (int I = 0; I <= wkArr.GetUpperBound(0); I++) {
            if (I < wkArr.GetUpperBound(0)) {
                AnswerList.Add(Math.Min(wkArr[I], wkArr[I + 1]));
            }
            else {
                AnswerList.Add(wkArr[I]);
            }
        }
        Console.WriteLine(
            string.Join(" ", AnswerList.Select(X => X.ToString()).ToArray()));
    }
}

解説

下記のロジックで貪欲法で解いてます。

 A-B-C
D-E-F-G

DはAとしてよい。
D>Aなら解なしになるし、
D<Aなら損である。

EはMin(A,B)としてよい。
E>Min(A,B)なら解なしになるし、
E<Min(A,B)なら損である。