Problem 287

Problem 287 「4分木符号化(シンプルな圧縮アルゴリズム)」 †

4分木による符号化を用いて, 2N×2N の白黒の画像を(0 と 1 の)ビット列で表すことができる. このビット列は左から右へ以下のようにして解読する:

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

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

この画像はいくつかの文字列で表すことができる, 例えば:
"001010101001011111011010101010" は長さ 30 であり, または
"0100101111101110", は長さ 16 であり, これはこの画像を表す最短のビット列である.

正の整数 N に対し, DN を次の条件を満たす 2N×2N の画像と定義する:

• 左下のピクセルを座標 x=0, y=0 とし,
• もし (x-2N-1)2+(y-2N-1)2 ≤ 22N-2 ならピクセルは黒とし,
• 他の場合はピクセルは白とする.

D24 を表す最短のビット列の長さを求めよ.