3.3 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4b41000cf542c50ffc7 | 問題 328: 最低コストを探す | 5 | 301985 | problem-328-lowest-cost-search |
--description--
整数 {1, 2, ..., $n$} から選ばれた秘密の数を、質問をすることで当てます。 それぞれの数 (質問) を尋ねるとき、尋ねた数と同じだけのコストがかかり、得られる答えは次の 3 つのいずれかです。
- 「あなたの推測は秘密の数よりも小さい」
- 「当たり！」
- 「あなたの推測は秘密の数よりも大きい」
値 n が与えられているとき、最適な戦略に従えば、起こり得る最悪のケースの総コスト (すなわち、尋ねた質問の総和) が最小化します。 次に例を示します。
n = 3 の場合、一番良いのはもちろん、秘密の数が "2" であるかどうかを尋ねることです。 答えを聞けば、すぐに秘密の数が分かります (総コスト = 2)。
n = 8 の場合は「二分探索」型の戦略が良いかもしれません。まず "4" を尋ね、秘密の数が 4 より大きければ、さらに 1 回か 2 回尋ねる必要があります。 2 回目は "6" を尋ねます。 秘密の数が 6 よりさらに大きければ、7 か 8 かを知るために 3 回目の質問が必要です。 したがって、3 回目の質問は "7" であり、この最悪ケースの総コストは $4 + 6 + 7 = \mathbf{\color{red}{17}}$です。
1 回目の質問で "5" を尋ねれば、n=8 に対する最悪ケースのコストを大幅に下げることができます。 秘密の数が 5 よりも大きいと言われた場合、2 回目の質問は「7」となり、秘密の数がどれなのかを確実に知ることができます (総コスト 5 + 7 = \mathbf{\color{blue}{12}})。 秘密の数が 5 よりも小きいと言われた場合、2 回目の質問は「3」となり、秘密の数が 3 より小さければ、3 回目の質問は "1" であり、総コストは 5 + 3 + 1 = \mathbf{\color{blue}{9}} です。 \mathbf{\color{blue}{12 > 9}} なので、この戦略における最悪ケースのコストは 12 です。 これは、先ほどの「二分探索」戦略の結果よりも優れています。また、他のどの戦略よりも優れているか、少なくとも同等です。 さて、ここまで n = 8 の最適な戦略を説明してきました。
上のとおり、n に対する最適な戦略によって達成される、最悪ケースのコストを C(n) とします。 したがって、C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12 です。
同様に、C(100) = 400, \displaystyle\sum_{n = 1}^{100} C(n) = 17575 です。
\displaystyle\sum_{n = 1}^{200\\,000} C(n) を求めなさい。
--hints--
lowestCostSearch() は 260511850222 を返す必要があります。
assert.strictEqual(lowestCostSearch(), 260511850222);
--seed--
--seed-contents--
function lowestCostSearch() {
return true;
}
lowestCostSearch();
--solutions--
// solution required