p11176.jpg

上図は整数の2進表示において、連続した1の並びの最大値の個数を表すもの。たとえば、3桁の2進数(つまり、整数0から7まで)は以下の通りだが、連続した1の並びの最大値は左から 0,1,1,2,1,1,2,3になっている。2進数101では、ビット1は2箇所にあるが、連続した1の並びの長さはそれぞれ1なので、全体としても1だ。

   000 001 010 011 100 101 110 111

そこで、同じ最大値のものをまとめて、最長値が0のものが1つ(000)、最長値が1のものが4つ(001,010,100,101)、最長値が2のものが2つ(011,110)、最長値が3のものが1つ(
111)になり、つまり 1 4 2 1という並び(上から3段目)が得られる。

ビット数をn、連続した1の並びの最長値をkとすると、整数それぞれにnとkはきまった対応関係になる。それを関数T(n,k)で表すと、つぎのような漸化式が成り立つ。

p11176-1.jpg

ただ、値がすぐに大きくなっていくので、多倍長整数か、実数を利用すること。

問題 UVa #11176 – Winning Streakを解くのに、こういう知識が勉強になる。

Comments are closed.

Post Navigation