1.9 KiB
1.9 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f54a1000cf542c51005c | 問題 477: 数列ゲーム | 5 | 302154 | problem-477-number-sequence-game |
--description--
数列ゲームは、一列に書かれた N 個の数からなる数列 S で始まります。
2 人のプレイヤーが交互にプレイします。 プレイヤーは自分のターンで、数列に残っている最初の数または最後の数を選択し、取り除きます。
取った数の和がそのプレイヤーのスコアになります。 各プレイヤーは自分の数の和を最大にしようとします。
N = 4 かつ S = \\{1, 2, 10, 3\\} の場合、各プレイヤーは次のようにスコアを最大化します。
- プレイヤー 1: 最初の数 (1) を取り除く
- プレイヤー 2: 残りの数列から最後の数 (3) を取り除く
- プレイヤー 1: 残りの数列から最後の数 (10) を取り除く
- プレイヤー 2: 残りの数 (2) を取り除く
プレイヤー 1 のスコアは 1 + 10 = 11 です。
次のように定義される数列 S = \\{s_1, s_2, \ldots, s_N\\} の最適な戦略に両プレイヤーが従った場合の、プレイヤー 1 のスコアを F(N) とします。
s_1 = 0s_{i + 1} = ({s_i}^2 + 45)mod1\\,000\\,000\\,007
数列は S = \\{0, 45, 2\\,070, 4\\,284\\,945, 753\\,524\\,550, 478\\,844, 894\\,218\\,625, \ldots\\} で始まります。
F(2) = 45, F= 4\\,284\\,990, F(100) = 26\\,365\\,463\\,243, F(104) = 2\\,495\\,838\\,522\\,951 が与えられます。
F({10}^8) を求めなさい。
--hints--
numberSequenceGame() は 25044905874565164 を返す必要があります。
assert.strictEqual(numberSequenceGame(), 25044905874565164);
--seed--
--seed-contents--
function numberSequenceGame() {
return true;
}
numberSequenceGame();
--solutions--
// solution required