AGC-006-B Median Pyramid Easy

■■■問題■■■

N段のピラミッドがあります。
段は上から順に 1, 2, ・・・, N と番号が振られています。

各 1 <= i <= N について、i段目には2i-1個のブロックが横一列に並んでいます。
また、各段の中央のブロックに注目すると、これらは縦一列に並んでいます。


N=4段のピラミッド

すぬけ君はN段目のブロックに (1, 2, ・・・, 2N-1) を並べ替えたもの(順列)を書き込みました。
さらに、次のルールに従い、残りすべてのブロックに整数を書き込みました。

●あるブロックに書き込まれる整数は、そのブロックの左下、真下、右下のブロックに書き込まれた整数の中央値である。


               ブロックに整数を書き込む例

その後、すぬけ君はすべてのブロックに書き込まれた整数を消してしまいました。
すぬけ君は、1段目のブロックに書き込まれた整数がxであったことだけを覚えています。

N段目のブロックに書き込まれた順列としてあり得るものが存在するか判定し、
存在するならばひとつ求めてください。

■■■入力■■■

N x

●2 <= N <= 10万
●1 <= x <= 2N-1

■■■出力■■■

N段目のブロックに書き込まれた順列としてあり得るものが存在しないならば、Noを出力せよ。
存在するならば、Yesを出力した後、2N-1行出力せよ。 このうちi行目には、順列のi番目の整数を出力せよ。

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 4");
            //Yes
            //1
            //6
            //3
            //7
            //4
            //5
            //2
            //問題文中の図の例です
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1");
            //No
            //N段目のブロックにどのような順列を書き込んでも、
            //1段目のブロックに書き込まれる整数は2となります。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        if (x == 1 || x == 2 * N - 1) {
            Console.WriteLine("No");
            return;
        }

        int[] TeihenArr = new int[2 * N - 1];
        int UB = TeihenArr.GetUpperBound(0);

        //中央の添字
        int CenterInd = UB / 2;

        int UseNum = 1;
        var sb = new System.Text.StringBuilder();
        sb.AppendLine("Yes");
        for (int I = 0; I <= UB; I++) {
            if (I == CenterInd - 1) {
                sb.Append(x - 1); sb.AppendLine();
            }
            else if (I == CenterInd) {
                sb.Append(x); sb.AppendLine();
            }
            else if (I == CenterInd + 1) {
                sb.Append(x + 1); sb.AppendLine();
            }
            else {
                while (x - 1 <= UseNum && UseNum <= x + 1) UseNum++;
                sb.Append(UseNum++); sb.AppendLine();
            }
        }
        Console.WriteLine(sb.ToString());
    }
}

解説

下記の4段のピラミッドであれば、

　　　Ｊ
　　ＧＨＩ
　□ＤＥＦ□
□□ＡＢＣ□□

Aがx以下、Bがx、Cがx以上ならば、
Dはx以下、Eがx、Fがx以上になり、
Gはx以下、Hがx、Iがx以上になり、
Jがxになるので、
Aにx-1,Bにx、Cにx+1を設定してます。