# 219 : 非対称コスト符号化

**A** と **B** をビット列(0と1の連続列)とする. **B**の左端から"**A**の長さ"ビットが**A**と一致する時, **A**を**B**の"接頭部"(prefix)と呼ぶ. 例えば 00110 は 001101001 の接頭部だが, 00111 や 100110 の接頭部ではない.

サイズ$$n$$の"接頭符号"(prefix-free code)とは, 次の条件を満たす $$n$$ 個の異なるビット列の集合である: どのビット列も他のビット列の接頭部ではない. 下の例はサイズ$$6$$の接頭符号である.

$$
0000, 0001, 001, 01, 10, 11
$$

ここでビット0を送るのに1ペニー, ビット1を送るのに4ペンスかかると仮定する. 上で挙げた接頭符号にかかる総計は35ペンスとなる. この例は非対称なコスト分布となるが, なんと(同じサイズの中で)もっとも安い符号の１つである. 短く書くと, $$\textrm{Cost}(6)=35$$ となる.

$$\textrm{Cost}(10^{9})$$を求めよ.

\[訳注 ペンス: ペニーの複数形]
