AGC032-A Limited Insertion

問題へのリンク

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("3");
            WillReturn.Add("1 2 1");
            //1
            //1
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("2 2");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9");
            WillReturn.Add("1 1 1 2 2 1 2 3 2");
            //1
            //2
            //2
            //3
            //1
            //2
            //2
            //1
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        var AnswerList = new List<int>();
        List<int> Blist = BArr.ToList();

        while (Blist.Count > 0) {
            bool IsMatch = false;
            for (int I = Blist.Count - 1; 0 <= I; I--) {
                if (Blist[I] == I + 1) {
                    IsMatch = true;
                    AnswerList.Add(Blist[I]);
                    Blist.RemoveAt(I);
                    break;
                }
            }
            if (IsMatch == false) {
                Console.WriteLine(-1);
                return;
            }
        }

        AnswerList.Reverse();
        AnswerList.ForEach(pX => Console.WriteLine(pX));
    }
}

解説

1 1 1 2 2 1 2 3 2
というサンプルで逆から考えます。

最後のInsertは1で、Insert前は
1 1 2 2 1 2 3 2 と分かります。

その前のInsertも1で、Insert前は
1 2 2 1 2 3 2 と分かります。

その前のInsertも1か2が考えられそうですが、
もし、1だとすると、Insert前の文字列は
2 2 1 2 3 2 になって、先頭の2が矛盾して、解になりえないので
Insertされた数値は2と分かり、Insert前は
1 2 1 2 3 2 と分かります。

同様にして、逆順に空文字列までたどっていければ、解あり
逆順に空文字列までたどっていけなければ、解なし
となります。