# 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)$$を求めよ。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://project-euler-ja.gitbook.io/project-euler-ja/301-400/321-330/p328.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.