328 : 最小コスト探索

整数の集合$\{1, 2, \dots, n\}$から選ばれた秘密の数を、質問により当てようとしている。数（質問）を尋ねる際は、尋ねた数に等しいコストがかかり、次の三つのいずれかの答えを得る：

• 「秘密の数はあなたの推測した数より小さいです」

• 「そう、まさにその数です！」

• 「秘密の数はあなたの推測した数より大きいです」

$n$の値が与えられたとき、最適な戦略をとると、起こり得る最悪の場合に対し、総コスト（尋ねた質問の全ての和）が最小になる。例えば、

$n=3$の場合、とり得る最良の方法はもちろん"2"と尋ねることである。答えによりたちどころに秘密の数が分かるだろう。総コストは2である。

$n=8$の場合、「二分探索」型の戦略を用いるべきだろう：最初の質問は"4"となり、もし秘密の数が4より大きければ、追加で1または2回の質問をする必要があるだろう。 2番目の質問を"6"としよう。秘密の数がなおも6より大きければ、7と8を見分けるため3番目の質問を必要とするだろう。 このようにして3番目の質問は"7"となり、この最悪の場合のシナリオに対する総コストは4+6+7=17となる。

最初の質問として"5"を尋ねると、$n=8$に対する最悪の場合のコストを大幅に改善することができる。 もし秘密の数は5より大きいと告げられた場合は、2番目の質問を"7"とすれば、秘密の数が何であるか確実に分かる。（総コストは 5+7=12） もし秘密の数は5より小さいと告げられた場合は、2番目の質問を"3"とすれば、もし秘密の数が3より小さければ3番目の質問は"1"となり、総コストは 5+3+1=9 となる。 12 > 9なので、この戦略に対する最悪の場合のコストは12となる。これは先ほどの「二分探索」の戦略の結果より優れている；また他のいかなる戦略より優れているか、同コストである。 以上の通り、$n=8$に対する最適な戦略を述べた。

上述のように、$n$に対し最適な戦略をとることで得られる最悪の場合のコストを$C(n)$とする。 $C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12$である。 同様に、$\displaystyle C(100) = 400, \sum_{n=1}^{100} C(n) = 17575$である。

$\displaystyle \sum_{n=1}^{200000} C(n)$を求めよ。