024号文書

主にプログラミング

ABC115 D - Christmas

問題

ABC115 D - Christmasです。

解法

求める解を f_N(X) で表します。

方針

解き方の方針は、 f_N(X) f_{N-1}の式で表すことです。 そのために、以下を解析します。

  • レベル  Lのバーガーの層数  a_L
  • レベル  Lのパティの枚数  b_L

レベルLのバーガーの層数

レベル Lのバーガーの定義より、以下の漸化式を得ます。

  •  a_0 = 1
  •  a_L = 1 + a_{L-1} + 1 + a_{L-1} + 1 = 2a_{L-1} + 3

これを解くと、 a_L = 2^{L + 2} - 3 を得ます。

レベルLのパティの枚数

レベル Lのバーガーの定義より、以下の漸化式を得ます。

  •  b_0 = 1
  •  b_L = b_{L-1} + 1 + b_{L-1} = 2b_{L-1} + 1

これを解くと、 b_L = 2^{L + 1} - 1 を得ます。

求める解

下から X層目について、以下の通り場合分けして解を求めます。

  • bottomのパン
  • bottomに近い方のレベル N - 1バーガー
  • 中央のパティ
  • topに近い方のレベル N-1バーガー
  • topのパン

例えば、

  •  Xが中央のパティならば、求める解は(bottomに近い方のレベル N-1バーガーのパティ数)+1が解、すなわち、 b_{N-1} + 1 が解です。
  •  Xがtopに近い方のレベル N-1バーガーならば、求める解は(bottomに近い方のレベル N-1バーガーのパティ数)+1+(topに近いほうのレベル N-1バーガーの下から(全体の底からみて) X層目までに含まれるパティ数)が解、 すなわち、 b_{N-1} + 1 + f_{N-1}(X - (1 + a_{N-1} + 1)) = b_{N-1} + 1 + f_{N-1}(X - a_{N-1} - 2) が解です。

 a_{L}, b_{L} は解析済みなので、  f_N(X) について、以下の漸化式を導出できます( N=0 の場合に注意してください)。

  •  N=0 のとき、 f_N(X) = 1
  •  N \geq 1, X=1 のとき、 f_N(X) = 0
  •  2 \leq X \leq 2^{N + 1} - 2 のとき、  f_N(X) = f_{N-1}(X - 1)
  •  X = 2^{N + 1} - 1 のとき、  f_N(X) = 2^N
  •  2^{N + 1} \leq X \leq 2^{N + 2} - 4 のとき、  f_N(X) = f_{N-1}(X - 2^{N + 1} + 1) + 2^N
  •  X = 2^{N + 2} - 3 のとき、  f_N(X) = 2^{N + 1} - 1

ACしたコード

Python3です。

N, X = map(int, input().split())

def f(n, x):
  if x == 1:
    return 1 if n == 0 else 0
  elif x <= 2**(n + 1) - 2:
    return f(n - 1, x - 1)
  elif x == 2**(n + 1) - 1:
    return 2**n
  elif x <= 2**(n + 2) - 4:
    return f(n -1, x - 2**(n + 1) + 1) + 2**n
  else:
     return 2**(n + 1) - 1

ans = f(N, X)
print(ans)