# 287 : 4分木符号化(シンプルな圧縮アルゴリズム)

4分木による符号化を用いて、$$2^N\times 2^N$$の白黒画像を（0と1の）ビット列で表すことができる。このビット列は左から右へ以下のようにして解読する：

* 最初のビットは$$2^N\times 2^N$$全体の領域を表す
* "0" は分割を意味する：\
  対象の$$2^n\times 2^n$$の領域を4つの$$2^{n-1}\times 2^{n-1}$$の領域に分割し、続くビット列は左上、右上、左下、右下の順で分割された領域を表す
* "10" は対象の領域が黒いピクセルしか含んでいないことを表す
* "11" は対象の領域が白いピクセルしか含んでいないことを表す

下の 4×4 の画像について考える（色のついた印はどこで分割が起こるかを表す）：

![](https://1547764285-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MCo5FMwYZBPuRk-sNIY%2F-Mh3Zs4NSi4lwevhF6_H%2F-Mh60IVKAEBlulpo7kVM%2Fimage.png?alt=media\&token=110fd73d-3ca4-4ce8-b60f-e88dc6b7cbf7)

この画像を表すビット列は複数存在する。例えば：\
"**0**(R)**0**(B)10101010**0**(G)1011111011**0**(o)10101010" は長さ 30 であり、または\
"**0**(R)10**0**(G)101111101110" は長さ 16 であり、これはこの画像を表す最短のビット列である。

(\* 文字に色を付ける代わりに(R)(B)(G)(o)を付記した、それぞれ赤緑青橙の意)

正の整数 N に対し、$$D_N$$を次の条件を満たす$$2^N\times 2^N$$の画像と定義する：

* 左下のピクセルを座標 x=0, y=0 とし、
* $$(x-2^{N-1})^2+(y-2^{N-1})^2 ≤ 2^{2N-2}$$なら(x,y)のピクセルは黒
* さもなくば(x,y)のピクセルは白

$$D^{24}$$を表す最短のビット列の長さを求めよ。
