【ABC115】D - Christmas

問題概要

レベルLのバーガーを以下のように定義する.

• レベル0のバーガーは, 'P'.
• レベルLのバーガー(L>=1)は, 'B' + (レベルL-1のバーガー) + 'P' + (レベルL-1のバーガー) + 'B'.

このとき, レベルNのバーガーの下からX層までに'P'は何個あるか求めよ.

制約

• 1 <= N <= 50
• 1 <= X <= (レベルNのバーガーの層の総数)

考察

Nがもっと小さければ単純に再帰書いて文字列作っていけばいいけど, Nが50まで行くから無理(最低2⁵⁰文字). 徐々に問題のサイズを小さくしていけば良さそう.

以下, レベルLのときのバーガーの層の総数をl[L], 'P'の個数をp[L]とする.

N=2のとき, BBPPPBPBPPPBB.

• Xが赤い文字に対応するときは, バーガーを完全に包含してるか, もしくは完全に含んでいないときなので, 再帰を終了.
• Xが青い文字に対応するときは, レベルN-1のバーガーの途中だから, レベルを1つ下げて再帰.

こんな感じのイメージで再帰を回す.

実装

Xは予め1引いて0から始まるようにした(なんかそっちのほうが単純そうだったので).

レベルNのとき, 赤い文字に対応するっていうことは, Xは0, l[N]/2, l[N]-1.

• X = 0のとき, 何も含んでないので何もせずに終了.
• X = l[N]/2のとき, レベルN-1のバーガーを1つ含んでいるので, res += p[N-1]+1をして終了(この+1は中心の'P').
• X = l[N]-1のとき, レベルNのバーガーを1つ含んでいるので, res += p[N]をして終了.

青い文字に対応するっていうことは, X > l[N]/2 と X < l[N]/2.

• X > l[N]/2のとき, レベルN-1のバーガーを1つ含んでいるため, まずそれを上のX=l[N]/2みたいに足して, X -= l[N-1]+2 (この括弧内の分: [BBPPPBP]BPPPBB).
• X < l[N]/2のとき, 何も含んでいないので何もせずに, X -= 1 (頭の'B'の分).

レベル0になったら, もうそれ以上分けられないから, res += 1して終了.

ACコード(Python3🐍)

n,x = map(int,input().split())
x -= 1

p = [1]
l = [1]
for i in range(n):
    p.append(p[-1]*2+1)
    l.append(l[-1]*2+3)

res = 0
while n >= 0:
    if n == 0:                 # レベル0のバーガーはこれ以上細分化できない
        res += 1
        break
    elif x == 0:               # 左端
        break
    elif x == l[n] - 1:        # 右端
        res += p[n]
        break
    elif x == l[n] // 2:       # 中心
        res += p[n-1] + 1
        break
    elif x > l[n] // 2:        # 1個包含している
        res += p[n-1] + 1
        x -= l[n-1] + 2
        n -= 1
    else:                      # 包含していない
        n -= 1
        x -= 1

print(res)