2013年11月17日日曜日

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

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

問87「3つの素数のべき乗」
素数の2乗と素数の3乗と素数の4乗の和で表される最小の数は28である. 
50未満のこのような数は丁度4つある.

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

では, 50,000,000未満の数で, 素数の2乗と素数の3乗と素数の4乗の和で表される数は何個あるか?





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






私の回答例は以下の通りです。
def p(n):
	L = [0,0]+[1]*(n-1)
	for i in xrange(n):
		if i*i>n: break
		if not L[i]: continue
		for j in xrange(i+i, n+1, i): L[j] = 0
	return [i for i in xrange(n+1) if L[i]]
def f(n):
	P, L = p(int((n-2**3-2**4)**.5)), []
	for i in P:
		for j in P:
			for k in P:
				s = k**2+j**3+i**4
				if n<=s: break
				L.append(s)
	return len(set(L))

n = 50000000
m = f(n)
print m


1.関数p(n)
・n以下の素数リストを返します。問37を流用しました。

2.関数f(n)
・素数の2乗と素数の3乗と素数の4乗の和で表されるn未満の数の個数を返します。

・Pに素数、Lには素数の2乗と素数の3乗と素数の4乗の和を格納します。
 ただし、使用する最大の素数は、自身の2乗と2の3乗と2の4乗の和がn未満になる最大素数なので、nから2の3乗と2の4乗を差し引いた値の平方根の整数部分です。
 この使用可能な最大素数までの素数をリストPに格納します。

・素数リストLから、3重のfor文でi,j,kとして順番に1つずつ、重複を許して取り出し、それぞれを2乗、3乗、4乗して、その和を変数sとします。

・変数sがnを超えたら、それ以上のkのループは不要なのでkのfor文を終了します。
 j,kのループにも同様の判定を入れることは可能ですが、1分ルールをクリアしたのでこのままとします。
 

・return len(set(L))
 set文でリストLの要素の値をユニークにして、len関数で個数を数えて戻します。

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

2013年11月16日土曜日

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

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

問86「直方体の道筋」
下に示す直方体は寸法が6×5×3である.
この直方体の1つの頂点Sにクモがいる. また反対の頂点Fにはハエがいる. 
SからFまでの壁に沿って直線移動する最短ルートは図に示す通りで, この長さは10である.

この最短ルートの候補は3本あるが, 最短のものがいつも整数長さとは限らない.
さて, M×M×M以下の寸法の直方体について, 最短ルートが整数である直方体の数を考える. 
M=100のとき, 条件を満たす直方体は2060個ある. このM=100は個数が2000を超える最小のMである. なお, M=99のときは1975個である.

100万個を超える最小のMを求めよ.





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






私の回答例は以下の通りです。
def f(n):
	m = c = 0
	while c<=n:
		m += 1
		k, L = m*m, []
		for i in xrange(2, m*2+1):
			s = (i*i+k)**.5
			if s==int(s): L.append(i)
		if not L: continue
		for i in L:
			c += i/2
			if m<i: c -= (i-m-1)
	return m, c

n = 1000000
m, c = f(n)
print "M:", m
print "num of routes:", c

反対側の頂点までの最短ルートの候補は、展開図で考えると以下の3つです。
直方体の各辺の長さをa,b,cとして、
・直角を挟む2辺が「a」「bとcの和」の直角三角形の斜辺:a2+(b+c)2 = a2+b2+c2+2bc
・直角を挟む2辺が「b」「cとaの和」の直角三角形の斜辺:b2+(c+a)2 = a2+b2+c2+2ca
・直角を挟む2辺が「c」「aとbの和」の直角三角形の斜辺:c2+(a+b)2 = a2+b2+c2+2ab

a≦b≦cとすると、最短ルートをsとして以下のとおりです。
s2 = a2+b2+c2+2ab = (a+b)2+c2 ・・・(A)

1.関数f(n)
・直方体のうち、各辺の長さと反対の頂点までの最短距離が整数長さのm×m×m以下の寸法で、その個数がn個を超える最小のmを返します。

・カウントすべき直方体の個数を変数cにカウントアップします。mとcはゼロクリアしておきます。

・whileループはカウントすべき直方体の個数cが限界値nを超えたら終了します。

・数え上げる直方体の最長辺がmなので式(A)は、a≦b≦c≦mという条件が付きます。最長辺の長さcをmとして、c2を変数kとします。

・for i in xrange(2, m*2+1):
 a+bの値を変数iとして1ずつ増やしていきます。
 この変数iの最小値はa=b=1のときで2、最大値はa=b=mのときなのでm*2です。
 xrange関数は第1引数から(第2引数-1)の値を第3引数(初期値1)刻みで発生させます。

・s = (i*i+k)**.5
 if s==int(s): L.append(i)
 式(A)を実装して、最短ルート長さsを求め、これをint関数で小数点以下切り捨てても同じ値かということで整数判定します。このsが整数ならばリストLにためます。

・if not L: continue
 上記ロジックでリストLが空の場合は整数長さの最短ルートがないので、現在のmでの探索は終了です。

・for i in L:
 c += i/2
 if m<i: c -= (i-m-1)
 これまでのロジックでリストLには題意に合うa+bの値をためていますので、1つずつ取り出して、a,bが整数になる組み合わせの個数を変数cに累計していきます。
 リストLから取り出した値iが2つの整数の和である組み合わせは、
 (1, i-1), (2, i-2), ..., (i-2, 2), (i-1, 1)
 の(i-1)通りで、真ん中以降は同じ組み合わせなので、異なる組み合わせとしては半分の(i-1)/2個です。i-1が奇数の場合は切り捨てます。

 リストLから取り出した変数iがm以下ならば、aとbの組み合わせは全部採用ですが、リストLには最大m*2までの値があるので、a,bの片方がmを超えてしまう分を差し引きます。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
M: 1818
num of routes: 1000457

2013年11月10日日曜日

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

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

問85「長方形の数え上げ」
注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている.

ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない. 一番近い解を持つような格子の面積を求めよ.






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






私の回答例は以下の通りです。
def f(n):
	xmax, sk, xk, yk = int((-1+(n*8+1)**0.5)/2), 1, 1, 1
	for x in xrange(1, xmax):
		t = x*(x+1)
		ys = int(((-t)+(t*t+16*t*n)**0.5)/2/t)
		for y in [ys, ys+1]:
			s = x*(x+1)*y*(y+1)/4
			if s==n: return x*y, x, y, s
			if abs(n-s)<abs(n-sk): sk, xk, yk = s, x, y
	return xk*yk, xk, yk, sk

n = 2000000
a, x, y, m = f(n)
print "area:", a
print "grid:", x,"x",y
print "num of rectangular:", m



格子が縦1個横x個の場合、含まれる長方形の数nは、1からnまでの和であり、
n = x(x+1)/2
これをxの二次方程式として解くと、
x2 + x - 2n = 0
x = (-1 ± √1-4x1x(-2n)) / 2
x>0より
x = (-1 + √1+8n) / 2 ・・・(A)

このxは、縦1個のときの横の個数で、横の個数の最大値xmaxとなります。
こうして、xのループを1からxmaxの値まで1つずつ変化させます。

縦x個横y個の格子に含まれる長方形の個数nは、
縦方向にx(x+1)/2、横方向にy(y+1)/2の積です。
n = x(x+1)/2 × y(y+1)/2
n = x(x+1)y(y+1)/4 ・・・(B)
ここで、t = x(x+1)と置くと、
n = ty(y+1)/4
n = (ty2 + ty)/4
ty2 + ty - 4n = 0

yの二次方程式として解くと、
y = (-t ± √(t2-4t(-4n))) / 2t
y>0より
y = (-t + √(t2+16nt)) / 2t
yは整数値なので、上記yの前後の整数、つまり上記yをint関数で切り捨てた値と、これに+1した値のいずれかが横の個数です。
上記の縦横の個数の候補の組み合わせで含まれる長方形の個数を計算し、ぴったりn個ならば終了、それ以外はnとの差の絶対値が小さいものをとっておきます。


1.関数f(n)
・n個の長方形を含む格子に一番近い解を持つ格子の面積、及びそのときの縦の個数、横の個数、長方形の数を返します。
 ただし、縦の個数は最も小さい値とします。

・xmax, sk, xk, yk = int((-1+(n*8+1)**0.5)/2), 1, 1, 1
 初期値設定します。縦個数の最大値xmaxとして上記式(A)を実装します。
 平方根はmathモジュールにsqrt関数もありますが、
 累乗演算子**で0.5乗しても同じです。

・ys = int(((-t)+(t*t+16*t*n)**0.5)/2/t)
 横個数の最大値ysとして上記式(C)を実装します。

・s = x*(x+1)*y*(y+1)/4
 含まれる長方形の数sとして上記式(B)を実装します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
area: 2772
grid: 36 x 77

num of rectangular: 1999998

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

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

問84「モノポリーの確率」 
モノポリーの標準的な盤面は以下である:

GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL
H2   C1
T2   U1
H1   C2
CH3   C3
R4   R2
G3   D1
CC3   CC2
G2   D2
G1   D3
G2J F3 U2 F2 F1 R3 E3 E2 CH2 E1 FP

各プレイヤーはGOのマスから開始し, 2個の6面サイコロを用いて時計回りに進む. 
他のルールが無いとすれば, 各マスに止まる確率は全て等しく, 2.5%である. 
しかし, G2J (Go To Jail), CC (Community Chest, 共同基金), CH (Chance, チャンス) のマスによってこの確率は変えられてしまう.

G2Jに止まる, または, CCやCHのマスに止まると引くカードのうちそれぞれ1枚によって, プレイヤーはJAILのマスに飛ばされる.
またプレイヤーが連続して3回ゾロ目を出すと, 3投目の結果のマスに進むのではなく, 直接JAILのマスに飛ばされる.
(筆者注:ぞろ目が連続して出る場合、連続が3回以内続く分の目の合計を進むのではなく、さいころを振る都度止まるマスの指示に従う)

ゲーム開始前にCCカードとCHカードはシャッフルされる.
プレイヤーがCCまたはCHマスに止まった場合, プレイヤーはCCカードまたはCHカードの山の一番上からカードを1枚引く. 
カードの指示に従ったのち, そのカードは山の一番下に戻される.
それぞれのカードは16枚あるが, 今回は問題を進み方に限定するので, 移動の指示があるカードのみを考える.
移動の指示が無いカードに関しては何もせずカードをそのまま山の下に戻す.
プレイヤーはそのままCC/CHマスに残るものとする.

Community Chest (16枚中2枚が移動カード) 
GOへ進め 
JAILへ進め
Chance (16枚中10枚が移動カード) 
GOへ進め 
JAILへ進め 
C1へ進め 
E3へ進め 
H2へ進め 
R1へ進め 
次のRへ進め (Rはrailway company, 鉄道会社の意) 
次のRへ進め 
次のUへ進め (Uはutility company, 公共事業会社の意) 
3マス戻れ
今回考えるのは, どのマスに止まりやすいかである. 
即ち, サイコロを投げた後に止まる確率である. 
より正確には, サイコロを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桁で表せ.





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






私の回答例は以下の通りです。
def f(n, d):
	import random
	#Board List
	BL = "GO A1 CC1 A2 T1 R1 B1 CH1 B2 B3 JAIL C1 U1 C2 C3 R2 D1 CC2 D2 D3 \
		FP E1 CH2 E2 E3 R3 F1 F2 U2 F3 G2J G1 G2 CC3 G3 R4 CH3 H1 T2 H2".split()
	BD = dict([(s, i) for i,s in enumerate(BL)])

	#Next Railway company
	L = [i for i,s in enumerate(BL) if s[0]=="R" and s[1:].isdigit()]
	NxR = [i for i,j in zip(L, [0]+L[:-1]) for k in xrange(i-j)]
	NxR += [NxR[0]]*(len(BL)-len(NxR))

	#Next Utility company
	L = [i for i,s in enumerate(BL) if s[0]=="U" and s[1:].isdigit()]
	NxU = [i for i,j in zip(L, [0]+L[:-1]) for k in xrange(i-j)]
	NxU += [NxU[0]]*(len(BL)-len(NxU))

	#community chest
	cc = [i for i,s in enumerate(BL) if s[:2]=="CC" and s[-1].isdigit()]
	ccL = [BD["GO"], BD["JAIL"]]+[""]*14
	random.shuffle(ccL)

	#chance
	ch = [i for i,s in enumerate(BL) if s[:2]=="CH" and s[-1].isdigit()]
	chL = [BD["GO"], BD["JAIL"], BD["C1"], BD["E3"], BD["H2"], BD["R1"], \
			"NxR", "NxR", "NxU", "bk3"]+[""]*6
	random.shuffle(chL)

	iCD = cntcc = cntch = p = 0
	B = dict([i, 0] for i in xrange(len(BL)))
	for i in xrange(n):
		d1, d2 = random.randrange(1, d+1), random.randrange(1, d+1)
		p = (p+d1+d2)%len(BL)

		#consecutive dobles
		if d1==d2:
			iCD += 1
			if iCD>=3: iCD, p = 0, BD["JAIL"]
		else: iCD = 0

		while True:
			#G2J
			if p==BD["G2J"]: p = BD["JAIL"]; break
			#JAIL
			elif p==BD["JAIL"]: break
			#comunity chest
			elif p in cc:
				t = ccL[cntcc]
				p = {True:t, False:p}[isinstance(t, int)]
				cntcc = (cntcc+1)%len(ccL)
				if p not in ch: break
			#chance
			elif p in ch:
				t = chL[cntch]
				t = {"NxR":NxR[p], "NxU":NxU[p], "bk3":p-3}.get(t,t)
				if isinstance(t, int): p = t
				cntch = (cntch+1)%len(chL)
				if p not in cc: break
			#etc.
			else: break

		B[p] += 1

	L = [t for t in sorted(B.items(), key=lambda x:x[1], reverse=True)]
	r = "".join([str(L[i][0]).zfill(2) for i in xrange(3)])
	P = [str(L[i][1]*100.0/n)[:4] for i in xrange(3)]
	return L, r, P

L, r, (p0, p1, p2) = f(1000000, 4)
print r, str(p0)+"%", str(p1)+"%", str(p2)+"%"


共同基金やチャンスカードがあるので数学的に確率を求めるのは難しいと思い、
PC上で十分に多い回数を試行することにしました。
6面さいころで試行したところ、さいころを100万回振ると、結果として、問題文中の値との差異が0.05%程度以内に収まりました。
そこで、4面さいころを100万回振ることで解を求めました。

1.関数f(n,d)
・モノポリーでd面さいころをn回振ることを試行し、止まった回数の多いマスのベスト3を6桁表示した値とそのマスに止まった割合を返します。

・最初に固定データをリストや辞書にします。
 盤面位置リストBL、マス名称から盤面位置を取得できる辞書BD、
 各マスごとに「次の鉄道会社」の位置のリストNxR、
 各マスごとに「次の公共事業会社」の位置のリストNxU、
 共同基金の位置リストcc、共同基金カードリストccL、
 チャンスの位置リストch、チャンスカードリストchL

・import random
 pythonにある乱数に関するいろいろな関数を使えるようにしておきます。

・ramdom.shuffle(ccL)
 共同基金カードリストccLをシャッフルします。最初にカードをよく切り混ぜるイメージです。チャンスカードも同様によく切り混ぜます。

・カウンタなどを初期設定しておきます。
 ぞろ目(consecusive doubles)の連続回数iCD、共同基金カードの現在使用位置cntcc、チャンスカードの現在使用位置cntch、盤面の現在位置pはゼロクリアしておきます。
 マス位置別に止まった回数カウンターを用意し辞書Bとし、各カウンタはゼロクリアしておきます。

・for i in xrange(n):
 さいころを振る回数iのループです。n回振ります。

・d1, d2 = random.randrange(1, d+1), random.randrange(1, d+1)
 d1とd2それぞれがさいころの目です。
 randrange関数で1からdまで整数を乱数発生させ、さいころの目とします。

・ぞろ目判定では、ぞろ目のときにぞろ目連続回数iCDをカウントアップし、ぞろ目以外の場合必ずゼロクリアすることで連続3回か判定しています

・共同基金とチャンスでは、出るカードによって進む先が再び共同基金やチャンスのことがあるので、連続してカードを引けるように無限ループに入れます。
どちらもこれ以外が出ればループから抜けます。

・共同基金カードは使用した位置をcntchで保持して1つずつ加算することで、カードの山の上から順番に使って使用後はカードの山の一番下に戻すイメージを実現しました。チャンスカードも同様です。

・L = [t for t in sorted(B.items(), key=lambda x:x[1], reverse=True)]
 sorted関数で並び替えた値を取り出して内包表記でリストLにします。
 sorted関数の引数は以下のとおりです。
・B.items()は、マス位置別に止まった回数カウンター辞書Bから、キー(マス位置)と値(止まった回数)の組のタプルを要素として取り出したリストです。
・key=lambda x:x[1]
 lambdaは無名関数で引数xを受け取り、x[1]、配列位置1つまり2番目の要素を返します。ここでは辞書Bをリスト化したデータを受け取り、止まった回数を返します。これがsorted関数での並び替えるキーとなります。
・reverse=Trueでsorted関数での並び順は降順、ここでは止まった回数の多い順となります。

・r = "".join([str(L[i][0]).zfill(2) for i in xrange(3)])
 止まった回数の多いベスト3の6桁表示値を求めます。
 止まった回数順に並び替えたリストLから、ループiで配列位置0から2番目の要素を取得します。ここでは止まった回数の多いベスト3の要素が取得されます。
 L[i][0]は対象のマス位置の数字なので、str関数で文字列にして、zfill関数で0埋めで2桁でします。
 さらに、このベスト3のマス位置の2桁値を、join関数で区切り文字なしで文字列連結します。

・P = [str(L[i][1]*100.0/n)[:4] for i in xrange(3)]
 止まった回数の多い方からベスト3の回数のパーセントを求めて、順に格納したリストです。


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

101524 7.04%% 3.65% 3.29% ※ベスト3の割合はたまたま実行したときの値です。


2013年10月27日日曜日

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

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

問83「経路の和:4方向」
注: この問題はProblem 81よりも非常に挑戦しがいがあるだろう.

下記の5次の正方行列で, 上下左右に移動し左上のセルから開始し右下のセルで終了する道を探索する. 一番小さな道は下で赤で示されており, このときの合計は2297になる.

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の行列が書かれている. 
上下左右に移動し左上のセルから開始し右下のセルで終了する道に沿った和の最小を求めよ.




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






私の回答例は以下の通りです。
def f(fn):
	import copy, sys
	L0 = open(fn).read().split("\n")
	L1 = [[int(t) for t in s.split(",")] for s in L0 if s]
	tn, yn = len(L1), len(L1[0])
	Ls = copy.deepcopy(L1)
	La = [[0 for j in xrange(yn)] for i in xrange(tn)]
	Lv = [["" for j in xrange(yn)] for i in xrange(tn)]
	Ld = [["" for j in xrange(yn)] for i in xrange(tn)]
	La[0][0] = 1
	while La[yn-1][tn-1]<2:
		smin = sys.maxint
		for i in xrange(tn):
			for j in xrange(yn):
				if La[i][j]==1 and Ls[i][j]<smin: smin, s, t = Ls[i][j], i, j
		i, j = s, t
		if i+1<tn \
		and (La[i+1][j]==0 or (La[i+1][j]==1 and Ls[i][j]+L1[i+1][j]<Ls[i+1][j])):
			Ls[i+1][j], La[i+1][j], Lv[i+1][j], Ld[i+1][j] \
			= Ls[i][j]+L1[i+1][j], 1, L1[i][j], "D"
		if 0<=i-1 \
		and (La[i-1][j]==0 or (La[i-1][j]==1 and Ls[i][j]+L1[i-1][j]<Ls[i-1][j])):
			Ls[i-1][j], La[i-1][j], Lv[i-1][j], Ld[i-1][j] \
			= Ls[i][j]+L1[i-1][j], 1, L1[i][j], "U"
		if j+1<yn \
		and (La[i][j+1]==0 or (La[i][j+1]==1 and Ls[i][j]+L1[i][j+1]<Ls[i][j+1])):
			Ls[i][j+1], La[i][j+1], Lv[i][j+1], Ld[i][j+1] \
			= Ls[i][j]+L1[i][j+1], 1, L1[i][j], "R"
		if 0<=j-1 \
		and (La[i][j-1]==0 or (La[i][j-1]==1 and Ls[i][j]+L1[i][j-1]<Ls[i][j-1])):
			Ls[i][j-1], La[i][j-1], Lv[i][j-1], Ld[i][j-1] \
			= Ls[i][j]+L1[i][j-1], 1, L1[i][j], "L"
		La[i][j] =2
		
	i, j, Mv, Md = tn-1, yn-1, [L1[tn-1][yn-1]], []
	while Ld[i][j]:
		Mv.insert(0, Lv[i][j])
		Md.insert(0, Ld[i][j])
		if Ld[i][j]=="D": i -= 1
		elif Ld[i][j]=="U": i += 1
		elif Ld[i][j]=="R": j -= 1
		elif Ld[i][j]=="L": j += 1
	
	return Mv, Md
	
import os
fn = os.path.join(os.path.dirname(__file__), "problem083_matrix.txt")
v, d = f(fn)
print "sum:", sum(v)
print "val:", v
print "dir:", d



問81や問82の方法ではとても1分ルールを守れそうにありません。
ネット検索して見つけた、ダイクストラの探索ロジックを参考にしました。

ダイクストラ法(wikipedia)

1.関数f(fn)
キーログファイルfnを分析して、最小和になる経路の各セルの値と次に曲がる方向を返します。

・リストL0にmatrixファイルの全データを行ごとに格納します。

・リストL1としてL0を行ごと値ごとの2次元配列にします。値は文字型から数値型にしておきます。
 ここで縦横の要素数をそれぞれtn, ynとします。

・リストLsには右端から遡ったときの通過セルの最小和を設定します。
 初期値としては上記L1を値コピーしておきます。
 Ls=L1とすると参照情報(ポインター)がコピーされ、値のコピーになりません。
 一次元配列のコピーは、Ls=L1[:]ですが、
 二次元配列のコピーはこれではうまくいきません。
 import copyしてから、copy.deepcopy()を使います。

・リストLaにはたどりで使った状況をデータと同じ配列位置に保持します。
 0:未使用、1:候補、2:最短経路として決定済み

・リストLvには最短経路たどりの際の直前値を格納します。

・リストLdには最短経路たどりの際に進む方向を格納します。


解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 425185
val: [4445, 1096, 20, 1318, 5115, 718, 2209, 2212, 654, 1443, 5741, 1585, 6935,
4497, 955, 101, 1478, 2509, 5436, 1732, 9480, 706, 707, 2679, 767, 714, 116, 93,
 1899, 328, 2876, 3604, 673, 158, 5093, 2447, 5782, 3967, 1716, 931, 239, 2000,
1228, 3513, 1909, 354, 2410, 1269, 3068, 5199, 2078, 617, 231, 2833, 4027, 396,
811, 2871, 3525, 6356, 3906, 1212, 5812, 345, 16, 691, 2388, 1383, 1555, 1833, 
739, 2100, 5800, 728, 4299, 10, 1929, 114, 6393, 9398, 265, 2622, 76, 2874, 880,
7270, 4071, 697, 9060, 3578, 1163, 1228, 2621, 3275, 2737, 7731, 486, 5726, 679,
 355, 1330, 2933, 985, 3200, 1663, 1456, 6846, 3120, 1211, 1622, 3176, 4524, 
 3996, 615, 2863, 1715, 242, 958, 3058, 584, 3234, 9688, 1549, 2917, 394, 3081,
 2581, 2994, 923, 2705, 4266, 3232, 2264, 6761, 363, 483, 556, 619, 3212, 3374, 
 3510, 1129, 3568, 2241, 2625, 2666, 4609, 1061, 2260, 3199, 1150, 1865, 1130,
 3144, 163, 6310, 2854, 3503, 3391, 6932, 1040, 5128, 1113, 3406, 7981]
dir: ['D', 'R', 'R', 'U', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R',
 'R', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'R', 'R', 'U', 'R', 'R', 'R', 'R',
 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'L',
 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R',
 'D', 'D', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D',
 'D', 'D', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'D', 'D',
 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R',
 'D', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D',
 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R',
 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'D',
 'D', 'D', 'D', 'D', 'R']

2013年9月30日月曜日

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

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

問82「経路の和:3方向」
注: この問題はProblem 81よりも挑戦しがいがあるだろう.

下記の5次の正方行列で, 一番左の行の任意のセルから開始し一番右の行の任意のセルで
終わる道を探索する. ただし上下右にのみ移動できるものとする. 
一番小さなパスは下で赤の太字で示されたものである. このときの合計は994になる.

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の行列が書かれている.
一番左の列から一番右の列へ移動する際の一番小さなパスの和を求めよ.




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






私の回答例は以下の通りです。

def f(fn): import copy L0 = open(fn).read().split("\n") L1 = [[int(t) for t in s.split(",")] for s in L0 if s] tn, yn = len(L1), len(L1[0]) L2 = copy.deepcopy(L1) L3 = [[""]*yn for s in xrange(tn)] for j in range(yn-1)[::-1]: for i in range(tn)[::-1]: d = {} r = L2[i][j+1] d[r] = "R" for k in range(i)[::-1]: s = 0 for m in xrange(k, i): s += L1[m][j] else: if r<s: break s += L2[k][j+1] d[s] = "U" for k in xrange(i+1, tn): s = 0 for m in range(i+1, k+1)[::-1]: s += L1[m][j] else: if r<s: break s += L2[k][j+1] d[s] = "D" s = min(d) L2[i][j] += s L3[i][j] = d[s] minsum = min([L2[i][0] for i in xrange(tn)]) for i in xrange(tn): if L2[i][0]==minsum: break sr, j,L4,L5 = i+1,0,[],[] while L3[i][j]: L4.append(L1[i][j]) L5.append(L3[i][j]) if L3[i][j]=="D": i += 1 elif L3[i][j]=="U": i -= 1 else: j += 1 L4.append(L1[i][j]) return sr, minsum, L4, L5 if __name__=="__main__": import os fn = os.path.join(os.path.dirname(__file__), problem082_matrix.txt") sr, s, val, dir = f(fn) print "start row:", sr print "sum:", s print "val:", val print "dir:", dir



問18問67問81を参考にしました。

1.関数f(fn)
・左端列から右端列に向かって上下右方向にのみ移動して通過したセルの最小和となるパスについて、開始行、合計、通過セルの値、たどり方向を返します。

・リストL0にmatrixファイルの全データを行ごとに格納します。

・リストL1としてL0を行ごと値ごとの2次元配列にします。値は文字型から数値型にしておきます。ここで縦横の要素数をそれぞれtn, ynとします。

・リストL2には右端から遡ったときの通過セルの最小和を設定します。
 初期値としては上記L1を値コピーしておきます。
 L2=L1とすると参照情報(ポインター)がコピーされ、値のコピーになりません。
 一次元配列のコピーは、L2=L1[:]ですが、二次元配列のコピーはこれではうまくいきません。
 import copyしてから、copy.deepcopy()を使います。

リストL3には左端から右端に向けて通過セルの和が最小になるようにたどるときの方向を格納します。初期値は要素がすべて""の二次元配列です。
 
・i,jの二重ループの中で左端列から右端列に向けて遡るように順にたどり、各セルから終点に向けて進んだときの最小和をリストL2に設定します。
 また最小和となる次の値の方向を上下右方向をそれぞれU,D,RとしてリストL4に設定します。
 

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
start row: 30
sum: 260324
val: [6223, 2099, 2700, 589, 4716, 8333, 1362, 5007, 2753, 478, 4341, 1031, 1046, 5127, 1570, 421, 276, 2650, 722, 916, 1596, 2241, 1626, 1384, 921, 2736, 7855, 173, 2065, 4238, 1048, 5, 2475, 5325, 6451, 924, 3328, 522, 90, 1124, 2679, 3241, 1162, 5812, 345, 16, 691, 2388, 1383, 1555, 1833, 739, 2100, 5800, 728, 4299, 10, 1929, 5897, 4188, 600, 1889, 3325, 65, 791, 5979, 2687, 2621, 2019, 8097, 1423, 3644, 4441, 2283, 684, 5396, 3193, 2955, 1088, 3801, 6203, 1748, 3737, 1276, 13, 1879, 2127, 2884, 5478, 4977, 3047, 2921, 106, 7508, 304, 1280, 1037, 1310, 966, 828, 3274, 1712, 3446]
dir: ['R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'U', 'R', 'R', 'R', 'U', 'R', 'R', 'U', 'R', 'U', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'R', 'R', 'U', 'R', 'R', 'D', 'D', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'R', 'U', 'U', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'U', 'R', 'R', 'R', 'R', 'R', 'U', 'U', 'U', 'R', 'R', 'R', 'R']

2013年8月25日日曜日

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

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

問81「経路の和: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の行列が書かれている. 
同様に左上のセルから開始し右下のセルで終わり, かつ右方向と下方向にのみ移動するときの最小のパスの和を求めよ.



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






私の回答例は以下の通りです。

def f(fn): import sys, copy L0 = open(fn).read().split("\n") L1 = [s.split(",") for s in L0 if s] tn, yn = len(L1), len(L1[0]) L2 = [[int(t) for t in s]+[sys.maxint] for s in L1]+[[sys.maxint]*yn] L3 = copy.deepcopy(L2) L4 = [["" for i in xrange(yn)] for j in xrange(tn)] for i in range(tn)[::-1]: for j in range(yn)[::-1]: if i==tn-1 and j==yn-1: continue elif L3[i][j+1]<L3[i+1][j]: L4[i][j]="R" elif L3[i+1][j]<=L3[i][j+1]: L4[i][j]="D" L3[i][j] += {"R":L3[i][j+1], "D":L3[i+1][j]}[L4[i][j]] i,j,L5,L6 = 0,0,[],[] while L4[i][j]: L5.append(L2[i][j]) L6.append(L4[i][j]) if L4[i][j]=="D": i += 1 else: j += 1 L5.append(L2[i][j]) return L3[0][0], L5, L6 import os fn = os.path.join(os.path.dirname(__file__),"problem081_matrix.txt") s, val, dir = f(fn) print "sum:", s print "val:", val print "dir:", dir



問18問67を参考にしました。

1.関数f(fn)
・下方向と右方向にのみ移動して通過したセルの最小和、そのパスを返します。

・リストL0にmatrixファイルの全データを行ごとに格納します。

・リストL1としてL0を行ごと値ごとの2次元配列にします。
 ここで縦横の要素数をそれぞれtn, ynとします。

・リストL2としてL1を数値化し、各列の最右端と最下段の要素を他の要素と同様に判定できるようにするために、各列の最右端と最下段に最大数値maxintを付加します。

・リストL3の初期値としてリストL2の値をコピーします。
 L3=L2とすると参照情報(ポインター)がコピーされ、値のコピーになりません。
 一次元配列のコピーは、L3=L2[:]ですが、
 二次元配列のコピーは、L3=L2[:][:]としてもうまくいきません。
 import copyしてから、copy.deepcopy()を使います。

・i,jの二重ループの中で右下から左上に向けて遡るように順にたどり、
 各値から終点に向けて進んだときの最小累積値をリストL3に設定します。
 また最小累積値となる次の値の方向を右方向R、下方向DをリストL4に設定します。

・始点から終点に向けて最小累積値になるように方向リストL4をたどっていき、
 リストL5にそれぞれの道筋の値を、リストL6に方向の値を設定していきます。
 

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
sum: 427337
val: [4445, 2697, 5115, 718, 2209, 2212, 654, 1443, 5741, 1585, 6935, 4497, 955, 101, 1478, 2509, 5436, 1732, 9480, 706, 496, 101, 5913, 93, 1899, 328, 2876, 3604, 673, 158, 5093, 2447, 5782, 3967, 1716, 931, 239, 2000, 1228, 3513, 1909, 354, 2410, 4171, 2709, 341, 5866, 106, 6379, 508, 811, 2871, 3525, 6356, 3906, 1212, 5812, 345, 16, 691, 2388, 1383, 1555, 1833, 739, 2100, 5800, 728, 4299, 10, 1929, 114, 6393, 9398, 265, 2622, 76, 2874, 880, 7270, 4071, 697, 9060, 3578, 1163, 1228, 2621, 3275, 2737, 7731, 486, 5726, 679, 355, 1330, 2933, 985, 3200, 1663, 1456, 6846, 3120, 1211, 1622, 3176, 4524, 3996, 615, 2863, 1715, 242, 958, 3058, 584, 3234, 9688, 1549, 2917, 394, 3081, 2581, 2994, 923, 2705, 4266, 3232, 2264, 6761, 363, 483, 556, 619, 3212, 3374, 3510, 1129, 3568, 2241, 2625, 2666, 4609, 1061, 2260, 3199, 1150, 1865, 1130, 3144, 163, 6310, 2854, 3503, 3391, 6932, 1040, 5128, 1113, 3406, 7981]
dir: ['R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'D', 'D', 'D', 'R', 'D', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'D', 'D', 'R', 'R', 'R', 'D', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'D', 'D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'D', 'R', 'D', 'R', 'R', 'R', 'R', 'D', 'D', 'R', 'D', 'R', 'D', 'D', 'D', 'D', 'D', 'D', 'D', 'R']

2013年8月15日木曜日

プロジェクトオイラー 問80別解

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

問80「平方根の10進展開」
よく知られているように、自然数の平方根が整数ではないならば、それは無理数である。
そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる。
2の平方根は1.41421356237309504880..., であり、
その頭から100桁の数字を合計すると475になる。

初めの100個の自然数の平方根のうち、無理数について、
それぞれの頭から100桁の数字を足した数の総和を求めよ。


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






私の回答例は以下の通りです。

def f(n, m): L, c = [i*i for i in xrange(n+1)], 0 for i in xrange(n+1): if i in L: continue x, a = i*10**m, i*10**(m*2) while x*x-a>1: x = (x+a/x)/2 c += sum([int(s) for s in str(x)[:m]]) return c n, m = 100, 100 print f(n, m)


平方根をニュートン法で求めます。
ニュートン法は方程式の解を近似計算する数値計算法です。
ニュートン法ではf(x)=0となるxを求める際に、xの近傍のxnでの接線とそのX軸との交点xn+1を順に求めていくことを繰り返してxの近似値を求めます。

(参考)
ニュートン法(wikipedia)

y=f(x)において、x=xnでの接線の傾きは微分係数f'(xn)なので以下の式が成り立ちます。
f(xn) = f'(xn) × (xn - xn+1)
式変形して、
xn+1 = Xn - f(xn)/f'(x)

当問題では平方根を求める元の数をaとして
f(x) = x2 - a としてf(x)=0となるxの近似値を求めます。
なお、xもaもそのままの値では小数点以下の桁が丸められてしまうので10のm乗倍などして大きな整数値にしてから処理して、x2 - a が1を超える場合に近似値を求め続けていきます。

開平法と比べ、ループ変数iの内側が簡単な式になっています。
処理時間も私の作った開平法ロジックと比べて30%程度です。


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

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

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

問80「平方根の10進展開」
よく知られているように、自然数の平方根が整数ではないならば、それは無理数である。
そのような平方根の10進展開(decimal expansion)は繰り返しを持たない無限小数になる。
2の平方根は1.41421356237309504880..., であり、その頭から100桁の数字を合計すると475になる。

初めの100個の自然数の平方根のうち、無理数について、それぞれの頭から100桁の数字を足した数の総和を求めよ。



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






私の回答例は以下の通りです。
def f(n, m):
	L, c = [i*i for i in xrange(n+1)], 0
	for i in xrange(n+1):
		if i in L: continue
		M, s, t = [], 0, i
		for j in xrange(m):
			N = [s*10+k for k in xrange(10)]
			for k in range(10)[::-1]:
				w = s*10+k
				if w*k<=t: break
			M.append(k)
			s, t = w+k, (t-w*k)*100
		c += sum(M)
	return c

n, m = 100, 100
print f(n, m)


平方根を開平法で求めます。

(参考)
開平法(wikipedia)

ルートを開こう(中村文則氏のサイト)


1.関数f(n, m)
・n個の自然数の平方根のうち、無理数について、それぞれの頭からm桁分の数字の和の総和を返します。

・リストLは自然数の2乗のリストで、その要素は平方根が有理数になる自然数す。

・変数cに求める総和を累積していきます。初期値は0です。

・ループ変数iが平方根を求める対象の自然数です。
 iがリストLに含まれている場合は対象外なので処理を飛ばします。

・リストMは平方根の各桁ごとの数字をためていくリストです。
・sは初期値0です。
・端数tは、元の数から、平方根を求めた桁までの2乗を差し引いた端数です。
 最初は平方根は1桁も求まっていないので、tの初期値はiです。

・ループ変数jは平方根の左端の桁位置を0とした桁位置を示します。

・for k in range(10)[::-1]:
w = s*10+k
if w*k<=t: break
 ループ変数kは、0から9までの配列を逆順に1つずつ取り出します。
 1つ前のループで計算したsの桁を1つ上げて(10倍して)kをたした値をwとし、
 wとkの積がtを超えない最大値となるkを探します。
 このkが平方根の求める桁の値です。

・s, t = w+k, (t-w*k)*100
 上記のkで1桁進みましたので次の桁の準備をします。
 wとkの和をsとします。
 新たに決定した桁の分である、wとkの積を端数tから差し引きます。
 100の平方根が10なので、平方根は元の数2桁ごとに1桁決まります。
 このため端数tは100倍しておきます。


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

2013年7月31日水曜日

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

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


問79「パスコードの導出」
オンラインバンクで通常使われるsecurity methodは,パスコードからランダムに選んだ3文字をユーザーに要求するものである.
たとえば, パスコードが531278のとき,2番目, 3番目, 5番目の文字を要求されるかもしれない. このとき, 期待される答えは: 317 である.

テキストファイルkeylog.txtには, ログインに成功した50回の試行が記録されている.
3つの文字が常に順番通りに要求されるとするとき, ファイルを分析して, 
可能なパスコードのなかでもっとも短いものを見つけよ.



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






私の回答例は以下の通りです。
def f(fn):
	L0 = open(fn).read().split()
	L1 = [[[],[]] for i in xrange(10)]
	for s in L0:
		t = [int(i) for i in s]
		for i in xrange(len(t)):
			for j in xrange(len(t)):
				if i!=j: L1[t[i]][int(i<j)].append(t[j])
	L2 = [[sorted(set(t)) for t in s] for s in L1]
	L3 = [[len(s[i]) for i in [0, 1]]+[j] for j, s in enumerate(L2)]
	L4 = sorted([s for s in L3 if s[0]+s[1]])
	L5 = [str(s[-1]) for s in L4]
	return "".join(L5)

if __name__=="__main__":
	import os
	fn = os.path.join(os.path.dirname(__file__), "problem079_keylog.txt")
	print f(fn)



1.関数f(fn)
・キーログファイルfnを分析して、最小文字列長のパスコードを返します。

・リストL0は、キーログファイルの全データを格納した配列リストです。

・リストL1は、各数字の左右にくる数字のリストを要素に持つリストです。
 [数字iの左にくる数字、数字iの右にくる数字]というリストをi番目の要素に持ちます。

・リストL2は、上記リストL1の二重配列の値をユニーク化して昇順に並べます。
 set関数で集合型にすることでユニーク化し、sorted関数でソートします。
 pythonの集合型は、ハッシュ値を持ち、値変更不可、重複値を持てない配列です。

・リストL3は、左右にくるユニーク値の個数のリストを要素に持つリストです。
 [数字iの右にくるユニーク値の個数、数字iの左にくるユニーク値の個数]というリストをi番目の要素に持ちます。

・リストL4は、上記リストL3から未使用数字を除去し、各数字の左にくるユニーク値の個数が少ない順に並べたリストです。
 具体的には左右のユニーク値の個数の和が正(論理的にTrue)の要素だけをリストL3から取り出して設定します。

・リストL5は、上記のリストL4の末尾要素に該当数字が格納されているので、それを文字型にしたリストです。

・ここまで処理して上記リストL5の要素を、連結文字なしで順に連結して返します。

2.関数の外
・fn = os.path.join(os.path.dirname(__file__), "problem079_keylog.txt")
 「__file__」はこのソースコードがあるプログラムファイルそのもののフルパスです。
 os.path.dirnameでこのフォルダを取得し、ファイルパスの区切り文字を挟みながら、キーログファイル名と結合します。

・print f(fn)
 関数fの戻り値を表示します。


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

2013年6月9日日曜日

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

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

問78「コインを山に分ける方法の数を調べ上げよ」
n 枚のコインを異なった方法で山に分ける場合の数を p(n) と表わす.
例えば, 5枚のコインを山に分ける異なったやり方は7通りなので p(5)=7 となる.

OOOOO

OOOO   O

OOO   OO

OOO   O   O

OO   OO   O

OO   O   O   O

O   O   O   O   O

p(n) が100万で割り切れる場合に最小となる n を求めよ.

-----


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






私の回答例は以下の通りです。
def f(n):
	L = [1]
	for j in xrange(1, n+1):
		r = 0
		for i in xrange(1, n+1):
			k = (i+1)//2 * ((i%2)*2-1)
			m = j - k*(k*3-1)//2
			if m<0: break
			r += ((i+1)%4//2*2-1) * L[m]
		if not r%n: return j, r
		L.append(r)
	return None
	
n=1000000
print f(n)



問76から3問連続で分割数の問題です。
それぞれ前の問を解決したロジックのままでは1分ルールに間に合いません。
ずいぶん考えたのですが、結果としてゼロから解法構築はできず、
ネット検索したロジックを実装しました。

wikipediaの「分割数」によれば以下のとおりです。
分割数の関数をpとして、
p(k) = p(k-1) + p(k-2) - p(k-5) - p(k-7) + p(k-12) + p(k-15) - p(k-22) - ...
p(0) = 1, 負の整数kに対してp(k)=0

関数pの引数の中で使用する値1, 2, 5, 7, 12, 15, ...は、
n=1, -1, 2, -2, 3, -3, 4, -4, ...に対する五角数n(3n-1)/2です。
また、p(k)を構成する各項の符号は、順に+, +, -, - の繰り返しです。

1.関数p(n)
・nで割り切れる最小の分割数を持つ整数とその分割数を返します。
・リストLは分割数の配列です。0以上の整数iの分割数をi番目の要素として持ちます。
・分割数リストLの初期値は、0の分割数で、定義により、1をセットします。
・ループ変数jごとに変数rに上記の各項の和rをためます。このrが整数jの分割数です。
・ループ変数iが分割数の式の各項に対応します。
 整数kの分割数は、k未満の分割数から計算できるので、
 ループ変数iは1からnまでの範囲内で負の数の分割数が必要になったところまでです。

ループ変数i
 1, 2, 3, 4, 5, 6, 7, 8, ... (A)

(i+1)//2
 1, 1, 2, 2, 3, 3, 4, 4, ... (B)

(i%2)*2 -1
 1,-1, 1,-1, 1,-1, 1,-1, ... (C)

よって、五角数を求めるための整数kは、(B)と(C)の積で、
k
 1,-1, 2,-2, 3,-3, 4,-4, ... (D)

そして上記(D)に対応する五角数は、
k*(3*k-1)//2
 1, 2, 5, 7,12,15,22,26, ... (E)

nから上記(E)の五角数を引いた値をmとして、mの分割数を求めます。
ループ変数j未満の分割数はすでに分割数リストLにあります。

求める分割数を構成する各項の和を求める際の、各項の符号は以下の通りです。
(i+1)%4//2*2-1
 1, 1,-1,-1, 1, 1,-1,-1, ... (F)

・分割数rがnで割り切れるか判定します。
  r%nでrをnで割った余りを求め、割り切れると余り0で論理的にFalseになります。
  このFalseになったときが割り切れたときで、整数jとその分割数rを返します。


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