FreeStyleWiki

プロジェクト・オイラー(081-085)

[プロジェクト・オイラー]

プロジェクト・オイラー(081-085)

  Problem 81

Probem 「経路の和:2方向」

 下記の5次の正方行列で, 左上のセルから開始し右下のセルで終わるパスを探索する.
 ただし下方向と右方向にのみ移動できるものとする.
 通過したセルの和が最小となるパスは赤の太字で示されたもので, その値は2427である.
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
 今, 31Kのテキストファイルmatrix.txt (右クリックして, 『名前をつけてリンク先を保存』)には80×80の行列が書かれている.
 同様に左上のセルから開始し右下のセルで終わり, かつ右方向と下方向にのみ移動するときの最小のパスの和を求めよ.

p081_matrix.txt(25)

Answer

+ 解答

  Problem 82

Probem 「経路の和:3方向」

 注: この問題はProblem 81よりも挑戦しがいがあるだろう.下記の5次の正方行列で,
 一番左の行の任意のセルから開始し一番右の行の任意のセルで終わる道を探索する. ただし上下右にのみ移動できるものとする. 
 一番小さなパスは下で赤の太字で示されたものである. このときの合計は994になる.
 今, 31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 一番左の行から一番右の行へ移動する際の一番小さなパスの和を求めよ.

Answer

+ 解答

  Problem 83

Probem 「経路の和:4方向」

 注: この問題はProblem 81よりも非常に挑戦しがいがあるだろう.下記の5次の正方行列で, 
 上下左右に移動し左上のセルから開始し右下のセルで終了する道を探索する. 
 一番小さな道は下で赤で示されており, このときの合計は2297になる.
 今, 31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 上下左右に移動し左上のセルから開始し右下のセルで終了する道に沿った和の最小を求めよ.

Answer

+ 解答

  Problem 84

Probem 「モノポリーの確率」

 モノポリーの標準的な盤面は以下である:各プレイヤーはGOのマスから開始し, 2個の6面サイコロを用いて時計回りに進む.
 他のルールが無いとすれば, 各マスに止まる確率は全て等しく, 2.5%である. しかし, G2J (Go To Jail),
 CC (Community Chest, 共同基金), CH (Chance, チャンス) のマスによってこの確率は変えられてしまう.G2Jに止まる,
 または, CCやCHのマスに止まると引くカードのうちそれぞれ1枚によって, プレイヤーはJAILのマスに飛ばされる.
 またプレイヤーが連続して3回ゾロ目を出すと, 3投目の結果のマスに進むのではなく, 直接JAILのマスに飛ばされる. 
 (訳注: モノポリーではゾロ目が出るともう1回サイコロをふる. 6,6→2,1の場合は合計15マス進む. 4,4→2,2→1,2の場合は合計15マス進む.
 3,3→4,4→2,2の場合は6マス目, 14マス目に止まったのちJAILに飛ばされる.)ゲーム開始前にCCカードとCHカードはシャッフルされる.
 プレイヤーがCCまたはCHマスに止まった場合, プレイヤーはCCカードまたはCHカードの山の一番上からカードを1枚引く.
 カードの指示に従ったのち, そのカードは山の一番下に戻される. それぞれのカードは16枚あるが, 今回は問題を進み方に限定するので, 
 移動の指示があるカードのみを考える. 移動の指示が無いカードに関しては何もせずカードをそのまま山の下に戻す.
 プレイヤーはそのままCC/CHマスに残るものとする.今回考えるのは, どのマスに止まりやすいかである.
 即ち, サイコロを投げた後に止まる確率である.
 
 より正確には, サイコロを1回振ってカードやマスによる移動を終えた後に各マスに止まる確率を求めたい.
 従って, G2Jに止まる確率は0であり, CHマスに止まる確率はその次に少ない(16枚中10枚が移動カードなので).
 またJAILマスにたまたま止まることとJAILマスに送られることを区別しない.
 またJAILマスから抜けるルール (自分のターンにゾロ目を2回出す) を無視する.
 つまり必ず保釈金を払ってJAILマスから進むものとする.GOマスを00とし番号を00-39と順番に振る.
 これにより各マスを2桁の数で表すことが出来る.統計的には, 3つのマスに止まりやすいことを示せる.
 JAIL (6.24%) = 10番目, E3 (3.18%) = 24番目, GO (3.09%) = 00番目である.
 従ってもっとも止まりやすいマスを6桁で表せて102400となる.2つの6面サイコロではなくて,
 2つの4面サイコロを用いた場合の, もっとも止まりやすいマスを6桁で表せ.
 (翻訳ヒント、サイコロを振りぞろ目だろうがでなかろうが止まったマス目の指示に従う。
 カードマスならカードを引く。これを繰り返す。繰り返す途中で三連続でぞろ目が出たら強制的に刑務所行き)

Answer

+ 解答

  Problem 85

Probem 「長方形の数え上げ」

 注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている.ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない. 
 一番近い解を持つような格子の面積を求めよ.

Answer

+ 解答