注意
はてなブログの仕様のため、タイトルはわざと全角文字にしています。
概要
タイトルの通り、pythonで「[0][0]」と入力すると0を出力する。
これは、[0]という長さ1の配列の0番目の値*1を出力するという意味なのでそうなる。
さらに、[[0][0]][[0][0]]も0になる。同様のノリで再帰的な構造を考えることができる
よって、
というコードを書くと、
0 [0][0] [[0][0]][[0][0]] [[[0][0]][[0][0]]][[[0][0]][[0][0]]] [[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]] [[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]] [[[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]]][[[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]]] [[[[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]]][[[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]]]][[[[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]]][[[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]][[[0][0]][[0][0]]]]][[[[[0][0]][[0][0]]][[[0][0]][[0][0]]]][[[[0][0]][[0][0]]]
[[[0][0]][[0][0]]]]]]]
…
となる。
つまり、以下のように定義される
文字列$\{S_n\}_{n=0}^{\infty}$において、
$S_0=''0''$
$S_{n+1}=''[''\quad+\quad S_{n}\quad+\quad ''][''\quad+ \quad S_{n}\quad+\quad '']''\quad(n\geq 0)$
このとき、$n$番目の列の長さは、$|S_0|=1,|S_{n+1}|=2|S_n|+4$を解けばよいため、
$$|S_n|=5\cdot 2^n-4$$
となる。
問題
$S_n$の先頭$m $文字の中に含まれている$''['',''0'','']''$の数をそれぞれ求めよ
制約
$0\leq n\leq 30000$
$0\leq m\leq \min\{5\cdot 2^n-4,10^{18}\}$
サンプル
n=30000
m=10^18のとき
400000000000017993 199999999999994012 399999999999987995
答えを$f:\mathbb{N}^2\to\mathbb{N}^3$とする。
また、$L_n=5\cdot 2^n-4$とする。
このとき、簡単な例から考えると、
$$f(0,0)=(0,0,0),f(0,1)=(0,1,0)$$
また、
$$f(n+1,L_{n+1})=(2,0,2)+2f(n,L_n)$$
より、
$$f(n,L_n)=(2^{n+1}-2,2^n,2^{n+1}-2)$$
となる。
$m\lt L_n$の場合は、$m\lt\dfrac{L_n}{2}$か$m\geq \dfrac{L_n}{2}$かで場合分けすればよい。
どちらの場合にせよ、$n\to n-1$とした場合の結果を流用すればOKである。
最終的にコードは以下のようになる。
計算量は考えてないけど、とりあえず上記の制約の場合手元では2秒以内に終了した。
問題の類題（ネタバレ注意）
