55 lines
1.8 KiB
Markdown
55 lines
1.8 KiB
Markdown
---
|
|
id: 5900f4fe1000cf542c510010
|
|
title: '問題 400: フィボナッチ木ゲーム'
|
|
challengeType: 5
|
|
forumTopicId: 302067
|
|
dashedName: problem-400-fibonacci-tree-game
|
|
---
|
|
|
|
# --description--
|
|
|
|
フィボナッチ木とは、次のように再帰的に定義される二分木です。
|
|
|
|
- $T(0)$ は空木である。
|
|
- $T(1)$ は 1 つのノードのみを持つ二分木である。
|
|
- $T(k)$ は、$T(k - 1)$, $T(k - 2)$ を子ノードとして持つ根ノードからなる。
|
|
|
|
このような木構造上で 2 人のプレイヤーが削除ゲームをします。 各ターンでプレイヤーがノードを選び、そのノードと、それを根とする部分木を削除します。 木全体の根ノードを取らざるを得なくなったプレイヤーが負けです。
|
|
|
|
$k = 1$ から $k = 6$ までの $T(k)$ において、最初のターンで先手必勝となる手は次のとおりです。
|
|
|
|
<img class="img-responsive center-block" alt="k = 1 から k = 6 の木における、最初のターンでの先手必勝の手" src="https://cdn.freecodecamp.org/curriculum/project-euler/fibonacci-tree-game.png" style="background-color: white; padding: 10px;" />
|
|
|
|
$T(k)$ の木構造でゲームをするとき、最初のターンにおける先手必勝の手 (すなわち、後手がどのような戦略でも勝てなくなるような手) の数を $f(k)$ とします。
|
|
|
|
例えば、$f(5) = 1$, $f(10) = 17$ です。
|
|
|
|
$f(10000)$ を求めなさい。 回答は、下位 18 桁とすること。
|
|
|
|
# --hints--
|
|
|
|
`fibonacciTreeGame()` は `438505383468410600` を返す必要があります。
|
|
|
|
```js
|
|
assert.strictEqual(fibonacciTreeGame(), 438505383468410600);
|
|
```
|
|
|
|
# --seed--
|
|
|
|
## --seed-contents--
|
|
|
|
```js
|
|
function fibonacciTreeGame() {
|
|
|
|
return true;
|
|
}
|
|
|
|
fibonacciTreeGame();
|
|
```
|
|
|
|
# --solutions--
|
|
|
|
```js
|
|
// solution required
|
|
```
|