2015年5月3日日曜日

プロジェクトオイラー 問109

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問109「ダーツ」
ダーツゲームでは, プレイヤーは 20 等分に分けられたダーツボードに 3 本のダーツを投げる. 
ダーツボードは 1 から 20 の番号がふられている.


ダーツの点数は, ダーツが刺さった領域の番号によって決まる. 
外側の赤緑の輪の外に刺さったダーツは 0 点である. 
この輪の内側の黒と白の領域はシングル (1 倍) の点数を表している. 
しかし, 外側と内側の赤緑の輪はそれぞれダブル (2 倍) とトリプル (3 倍) の点数である.

ボードの中央の 2 つの同心円はブルやブルズアイと呼ばれる. 
外側のブルは 25 点, 内側のブルはダブルの 50 点である.

ルールには多くのバリエーションがあるが, 最もポピュラーなゲームでは, 
プレイヤーは 301 または 501 点から始まり, 最も早く現在の得点を 0 点に減らしたプレイヤーが勝者となる. 
しかし, 普通は「ダブルアウト」方式でプレイをする. 
この方式では, プレイヤーは勝利するために, 
最後のダーツをダブル (ボードの中央のダブルのブルズアイを含む) に刺さなければならない. 
それ以外で現在の得点を 1 点以下に減らした場合, 
3 本のダーツに対する得点は「バースト(無効)」になる.

プレイヤーが現在の得点で終了できる場合を「チェックアウト」と呼ぶ. 
最も高いチェックアウトは 170: T20 T20 D25 (トリプルの 20 を 2 回とダブルのブル) である.

得点が 6 でチェックアウトする異なるやり方はちょうど 11 通りある.

D3   
D1 D2  
S2 D2  
D2 D1  
S4 D1  
S1 S1 D2 
S1 T1 D1 
S1 S3 D1 
D1 D1 D1 
D1 S2 D1 
S2 S2 D1 

D1 D2 と D2 D1 は, 異なるダブルで終了しているので異なるとみなすことに注意しよう. 
しかし S1 T1 D1 の組み合わせは T1 S1 D1 と同じとみなす.

さらに, 組み合わせを考える上でミスは含まないこととする; 
たとえば, D3 は 0 D3 や 0 0 D3 と同じである.

信じられないことに, 異なるチェックアウトは全部で 42336 通りある.
得点が 100 未満の異なるチェックアウトは何通りあるか.






注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。
def f(n):
	Ls = [i+1 for i in xrange(20)]+[25]
	Ld = [(i+1)*2 for i in xrange(20)]+[50]
	Lt = [(i+1)*3 for i in xrange(20)]
	La = Ls+Ld+Lt
	c = 0

	for i in Ld:
		if i<n: c += 1

	for i in La:
		for j in Ld:
			if i+j<n: c += 1

	for m, i in enumerate(La):
		for j in La[m:]:
			for k in Ld:
				if i+j+k<n: c += 1

	return c

n=100
c = f(n)
print c


何投目で終了するかの別に分けてカウントします。

1.関数f(n)
・n点未満でチェックアウトするときの、場合の数を返します。
・リストLsはシングルの得点リストです。要素は1から20までの整数と25です。
・リストLdはダブルの得点リストです。要素は1から20までの偶数と50です。
・リストLtはトリプルの得点リストです。要素は1から20までの3の倍数です。
・リストLaは全面の得点リストです。
 シングル、ダブル、トリプルのリストを単純に結合したものです。

・1投終了の場合、ダブルのリストLdです。
 この中から得点合計がn未満の場合をカウントします。

・2投終了の場合、1投目は前面リストLa、2投目はダブルのリストLdです。
 二重ループで状況を再現し、得点合計がn未満の場合をカウントします。

・3投終了の場合、
 1投目は前面リストLa、
 2投目は前面リストLaのうち1投目としてカウントしてないもの、
 つまり、リストLaから1投目で採用した位置よりも後の位置で採用します。
 3投目はダブルのリストLdです。
 三重ループで状況を再現し、得点合計がn未満の場合をカウントします。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
38182

0 件のコメント:

コメントを投稿