D - Christmas

はじめに

競技プログラミング、AtCoder Beginner Contest 115
D - Christmas
言語はC#
何かあればTwitter→@pirorirori_n712まで
※手抜きです、分かりにくいかもしれません。

問題

問題文

とある世界では、今日はクリスマスです。

高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル L バーガー (L は 0 以上の整数) とは次のようなものです。

・レベル 0 バーガーとは、パティ 1 枚である。
・レベル L バーガー (L≥1) とは、バン 1 枚、レベル L−1 バーガー、パティ 1 枚、レベル L−1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。

例えば、パティを 'P' 、バンを 'B' で表すと、レベル 1 バーガーは 'BPPPB' (を 90 度回転したもの)、レベル 2 バーガーは 'BBPPPBPBPPPBB' といった見た目になります。

高羽氏が作るのはレベル N バーガーです。ダックスフンドのルンルンは、このバーガーの下から X 層を食べます (パティまたはバン 1 枚を 1 層とします)。ルンルンはパティを何枚食べるでしょうか？

制約

・1≤N≤50
・1≤X≤( レベル N バーガーの層の総数 )
・N,X は整数である。

入力

入力は以下の形式で標準入力から与えられる。
N X

出力

レベル N バーガーの下から X 層に含まれるパティの枚数を出力せよ。

解き方

まず、単純にNバーガーの文字列を作り上げて
K回ループを回して解こうとすると数が大きすぎてTLEします。
ならば、と以下の方法を参考にして
int.MaxValueを引きながら回してみたのですが
こちらはOutOfMemoryしました。

stackoverflow.com

ループを回す回数を少なくするために、再帰的に解くことが必要です。
この問題のポイントは問題文のポイントの以下の部分です。

レベル L バーガー (L≥1) とは、バン 1 枚、レベル L−1 バーガー、パティ 1 枚、レベル L−1 バーガー、バン 1 枚、をこの順に下から積み重ねたもの

この一文から、
L-1バーガーが分かればLバーガーを求めることができることが分かります。

・レベル0バーガー（問題文よりパティのみ）
P

↓

・レベル1バーガー
B+レベル0バーガー+P+レベル0バーガー+B＝BPPPB

↓

・レベル2バーガー
B+レベル1バーガー+P+レベル1バーガー+B＝BBPPPBPBPPPBB

また同じように、
Lバーガーが分かればL-1バーガーを求めることも可能です。

・レベル2バーガー
BBPPPBPBPPPBB

↓

・レベル1バーガー
レベル2バーガー＝B+レベル1バーガー+P+レベル1バーガー+B
BBPPPBPBPPPBB＝B+レベル1バーガー+P+レベル1バーガー+B
B+BPPPB+P+BPPPB＝B+レベル1バーガー+P+レベル1バーガー+B
BPPPB＝レベル1バーガー

↓

・レベル0バーガー
レベル1バーガー＝B+レベル1バーガー+P+レベル0バーガー+B
BPPPB＝B+レベル0バーガー+P+レベル0バーガー+B
B+P+P+P＝B+レベル0バーガー+P+レベル0バーガー+B
P＝レベル0バーガー

つまり、
Lバーガーが分かれば常にL-1バーガーが分かります。

これを利用してレベルNバーガーから
だんだん下に下がっていく（N、N-1、N-2…0）
再帰的な解き方をすればループを回す回数は
最大でもN回になります。
再帰処理については、以下の記事が分かり易いです。

betrue12.hateblo.jp
では、
どのように再帰的に解いていくかというと
Lバーガーから常にL-1バーガーが分かる、
すなわちパティの数が分かるということを利用します。

レベル2バーガーを例にして、
パティの数についての場合分けを見ていきます。

ここでまず、レベル2バーガーが以下であること、
かつレベル0～2までのパティの数が分かっているとします。
（どちらもレベル0から2回ループを回して保存しておきます）

BBPPPBPBPPPBB

このうち、
レベル1バーガーは以下の赤枠で囲った部分です。

ここから、
バーガーを分解しながらバーガーの構造と
パティの位置に注目しながら考えていきます。

まず、
レベル1バーガーのパティの数が保存してあるので
3であることは既に分かっています。
そして、
一番下と上のバンズは問題文より
レベル0からバーガーのレベルが1増える度に1ずつ増えていきます。
また真ん中のパティは常に1つずつ増えていきます。
今目の前にあるバーガーをレベルNバーガーだとすると
構造は以下のようになります。

レベルNバーガー
N個のバンズ+レベルN-1バーガー+パティ+レベルN-1バーガー+N個のバンズ
=B×N+レベルN-1バーガー+P+レベルN-1バーガー+B×N

ここから、
Nバーガーと言われた時点で
下と上のバンズの数が分かります。

そして、問題のパティですが
レベルN-1バーガーのパティの数が分かるので
そこを基準に考えていきます。

レベル1バーガーとレベル2バーガーを書き出してみると
以下のようになることが分かります。

レベル1バーガー
BPPPB

レベル2バーガー
BBPPPBPBPPPBB

構造に注目すると
常にパティが真ん中にくることが分かります。
そして、このパティはレベルN-1バーガーのものではなく
Nバーガーで足されたものです。


ここで、
今までの情報で分かっているものを整理します。
バーガーをNバーガーとすると
・N-1のパティの数
・下と上のパティの数
・Nで追加されたパティが常に真ん中にくる

ここでパティの数を求めるための
場合分けを考えます。

・下のパティの数が分かる
→レベルNバーガーでKがN以下であればパティは0枚
レベル2バーガー（N=2）であれば以下のようになります。

レベル2バーガーは下のバンズが2枚なので
Kが2以下であれば、パティは0枚だと分かります。

・下のパティの数とレベルNバーガーのパティの数が分かる
→Kの数が真ん中-1、或いは真ん中-2であれば、
パティの数はN-1バーガーの数と同じです。
レベル2バーガー（N=2）であれば以下のようになります。

Kが5か6であればレベル1バーガーのパティの数＝3となります。

・Nバーガーの常に真ん中はパティ
→Kが真ん中の値であればレベルN-1バーガーのパティ+1
レベル2バーガー（N=2）であれば以下のようになります。

Kが７であればレベル1バーガーのパティの数+1＝3+1＝4となります。

・上のパティの数が分かる
→Kが真ん中よりも大きい
かつ、レベルNバーガー全体の大きさからN引いた数以上の数であれば
パティの数は
レベルN-1バーガーのパティの数+真ん中のパティ+レベルN-1バーガーのパティの数となります。
レベル2バーガー（N=2）であれば以下のようになります。

Kが13-2＝11以上であれば、
レベル1バーガーのパティ+真ん中のパティ+レベル1バーガーのパティ＝3+1+3＝7となります。

上の場合に当てはまらないものは、
KがレベルN-1バーガーの途中だった場合です。
レベル2バーガーであれば
上のどれにも当てはまらないKの値は以下の通り348910です。

この場合は再帰させます。

つまり、
Kの値をN-1バーガーならどこにあたるかを考えて変化させ
上と同じ処理をします。
また、そこでも
上のどの場合にもあてはまらなければ
またNから1を引いて次のバーガーの場合で処理をします。
ここで一つ気を付けなければいけない点は、
下のレベルN-1バーガーと
上のレベルN-1バーガーでは処理が違うということです。
なぜならば、
レベルN-1バーガーに処理を回してしまった場合、
下のN-1バーガーは問題ないですが
上のN-1バーガーは下に含まれているパティの情報を
N-1バーガーにもっていくことができないからです。
そのため、
上のN-1バーガーの途中に
Kの値がある場合は
下のN-1バーガーのパティの数+真ん中のパティの数を保存しておきます。
レベル2バーガーの場合、以下のようになります。


どんどんNの値を小さくしていき、
上の処理を繰り返せばいつかは
上の処理のどこかの場合になるので処理が終わります。

コード

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

class Dmondai
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var N = line[0];
        var K = line[1];

        //バーガー全体の数
        var bArray = new long[N + 1];
        bArray[0] = 1;
        //パティの数
        var pArray = new long[N + 1];
        //レベル0バーガー
        pArray[0] = 1;
        //Nバーガーまでの情報を保存する
        for (long i = 1; i <= N; ++i)
        {
            //Nバーガー全体の数
            //バンズ+N－1バーガー+パティ+N-1バーガー+バンズ
            bArray[i] = bArray[i - 1] * 2 + 3;
            //Nバーガーのパティの数
            //N-1バーガー+パティ+N-1バーガー
            pArray[i] = pArray[i - 1] * 2 + 1;
        }

        //答え格納用変数
        var ans = 0L;
        //Kの値を保存
        var k = K;
        //レベルNバーガーからレベル0バーガーまで、
        //再帰処理をするためのループ
        for (var i=N;-1<i;--i) {
            //真ん中の数を出す
            var num = (bArray[i] + 1) / 2;
            //Kがの値が下のバンズだけの場合
            if (k <= i)
            {
                break;
            }
            //Kが真ん中-1、或いは真ん中-2の場合
            //パティの数はN-1バーガー
            else if ((num - 1) == k || (num - 2) == k)
            {
                ans += pArray[i - 1];
                break;
            }
            //Kが真ん中のとき
            else if (num == k)
            {
                ans += pArray[i - 1] + 1;
                break;
            }
            //Kの値が全体-Nのとき
            //パティの数はレベルN-1+1+レベルN-1
            else if (bArray[i] - i <= k)
            {
                ans += pArray[i];
                break;
            }
            //上以外の場合
            //再帰処理をかける
            else {
                //真ん中よりもKが大きければ上のN-1レベルバーガーのとちゅうなので
                //答えにレベルN-1バーガー+1を足して保存しておく
                if (num < k)
                {
                    ans += pArray[i - 1] + 1;
                    //Kから真ん中までの数を引けば
                    //N-1の中でのKの値になる
                    k -= num;
                }
                else
                {
                    //下のN-1バーガーの途中の場合は
                    //一番下のバンズだけ引いておく
                    --k;
                }
            }
        }
        Console.WriteLine(ans);
    }
}