> For the complete documentation index, see [llms.txt](https://project-euler-ja.gitbook.io/project-euler-ja/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://project-euler-ja.gitbook.io/project-euler-ja/301-400/321-330/p328.md).

# 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)$$を求めよ。