Problem 477
の編集
http://odz.sakura.ne.jp/projecteuler/index.php/skin/pukiwiki.css?Problem+477
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
(no template pages)
*[[Problem 477:http://projecteuler.net/problem=477]] 「数列ゲーム」 [#b6326f65] 数列ゲームは一列に書かれた '''N''' 個の数からなる数列 '''S''' から始まる. 2人のプレーヤーが交互にターンを交代する. ターンが来ると, プレーヤーは数列に存在する先頭か末尾の数のどちらかを選択し取り除く. プレーヤーの得点は取り除いた全ての数の合計となる. それぞれのプレーヤーは自身の得点の合計を最大化するよう努める. '''N''' = 4, そして '''S''' = {1, 2, 10, 3} のとき, 以下のようにそれぞれのプレーヤーは自身の得点を最大にしていく: - プレーヤー 1: 先頭の数を取り除く (1) - プレーヤー 2: 残りの数列から末尾の数を取り除く (3) - プレーヤー 1: 残りの数列から末尾の数を取り除く (10) - プレーヤー 2: 残りの数を取り除く (2) プレーヤー 1 の得点は 1 + 10 = 11 となる. 下記のように定義された数列 '''S''' = {'''s'''&sub{1};, '''s'''&sub{2};, ..., '''s'''&sub{'''N'''};} においてプレーヤー双方が最適な戦略に従った時のプレーヤー 1 の得点を '''F'''('''N''') としよう: - '''s'''&sub{1}; = 0 - '''s'''&sub{'''i'''+1}; = ('''s'''&sub{'''i'''};&sup{2}; + 45) modulo 1 000 000 007 この数列は '''S''' = {0, 45, 2070, 4284945, 753524550, 478107844, 894218625, ...} から始まる. '''F'''(2) = 45, '''F'''(4) = 4284990, '''F'''(100) = 26365463243, '''F'''(10&sup{4};) = 2495838522951 が与えられている. '''F'''(10&sup{8};) を求めよ.
タイムスタンプを変更しない
*[[Problem 477:http://projecteuler.net/problem=477]] 「数列ゲーム」 [#b6326f65] 数列ゲームは一列に書かれた '''N''' 個の数からなる数列 '''S''' から始まる. 2人のプレーヤーが交互にターンを交代する. ターンが来ると, プレーヤーは数列に存在する先頭か末尾の数のどちらかを選択し取り除く. プレーヤーの得点は取り除いた全ての数の合計となる. それぞれのプレーヤーは自身の得点の合計を最大化するよう努める. '''N''' = 4, そして '''S''' = {1, 2, 10, 3} のとき, 以下のようにそれぞれのプレーヤーは自身の得点を最大にしていく: - プレーヤー 1: 先頭の数を取り除く (1) - プレーヤー 2: 残りの数列から末尾の数を取り除く (3) - プレーヤー 1: 残りの数列から末尾の数を取り除く (10) - プレーヤー 2: 残りの数を取り除く (2) プレーヤー 1 の得点は 1 + 10 = 11 となる. 下記のように定義された数列 '''S''' = {'''s'''&sub{1};, '''s'''&sub{2};, ..., '''s'''&sub{'''N'''};} においてプレーヤー双方が最適な戦略に従った時のプレーヤー 1 の得点を '''F'''('''N''') としよう: - '''s'''&sub{1}; = 0 - '''s'''&sub{'''i'''+1}; = ('''s'''&sub{'''i'''};&sup{2}; + 45) modulo 1 000 000 007 この数列は '''S''' = {0, 45, 2070, 4284945, 753524550, 478107844, 894218625, ...} から始まる. '''F'''(2) = 45, '''F'''(4) = 4284990, '''F'''(100) = 26365463243, '''F'''(10&sup{4};) = 2495838522951 が与えられている. '''F'''(10&sup{8};) を求めよ.
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
