ABC422-D Least Unbalanced

問題へのリンク

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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long K = wkArr[1];

        long FinalLen = (long)Math.Pow(2, N);

        var PrevList = new List<long>();
        PrevList.Add(K);

        while (PrevList.Count < FinalLen) {
            var CurrList = new List<long>();
            foreach (long EachVal in PrevList) {
                long Val1 = EachVal / 2;
                long Val2 = EachVal / 2;
                if (EachVal % 2 == 1) {
                    Val1++;
                }
                CurrList.Add(Val1);
                CurrList.Add(Val2);
            }
            PrevList = CurrList;
        }

        if (PrevList.Distinct().Count() == 1) {
            Console.WriteLine(0);
        }
        else {
            Console.WriteLine(1);
        }
        Console.WriteLine(LongEnumJoin(" ", PrevList));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

完全二分木を意識しつつ、
木の根から葉に向かって、2で割った値を配ってます。