Project Eulerのメモ - Readme sometime

Project Euler 240

{1,...,i}からn個をとった上位t個の和がsになる出方の個数をf(i,n,t,s)とする.
f(12,20,10,70)の値を求めたい.

まず{1}からn個とったうち上位t個の和がtになる出方は1通り, 和がそれ以外になるのは0通り.

{1,...,i}からn個をとった上位t個の和がsになるのは, t個全部がiの場合とt個のうちk個(0<=k<=t-1)がiの場合がある.
t個のうちk個がiになる場合は, 「{1,...,i-1}からn-k個をとった上位t-k個の和がs-ikになる並び」にk個のiをねじ込むとできる.
t個が全部iになる場合はi*t == sの場合しかなくて, 「{1,...,i-1}からn-k個をとった並び」にk個のiをねじ込むとできる.
また, n-k個の並びにk個のiをねじ込む仕方は ${_{n-k+1} \mathrm{H} _k = {_n \mathrm{C} _k}}$ 通りある

よって
$f(1,n,t,t) = 1$
i*t == sのとき $f(i,n,t,s) = \sum_{k=0}^{t-1} {_n\mathrm{C}_k} f(i-1,n-k,t-k,s-ik) + \sum_{k=t}^{n} {_n\mathrm{C}_k} (i-1)^{n-k}$
i*t != sのとき $f(i,n,t,s) = \sum_{k=0}^{t-1} {_n\mathrm{C}_k} f(i-1,n-k,t-k,s-ik)$

高速化のためにメモ化したり, i*t < sのときは必ず0なので打ち切ったりする.

Project Euler 293

10^9未満のadmissible numberのリストを作成して, それぞれに対してpseudo-Fortunate numberを求める.

i番目の素数を含むadmissible numberのリストをf(i)とする. 便宜的にf(1)=[1]とすると
i+1番目の素数をpとして
f(i+1) = f(i-1).map{|n| n*p }+f(i-1).map{|n| n*p^2 }+...+f(i-1).map{|n| n*p^m }
ただし, n*p^m < 10^9 <= n*p^(m+1)
でadmissible numberが求められる.

pseudo-Fortunate numberは素直に素数のリストを引くか, 2ずつ増やして素数判定を行って調べる.
チェビシェフの定理によれば任意の自然数nについてn+1 < p < 2(n+1)を満たす素数pが必ず存在するから
sqrt(2*10^9)までの素数表があれば十分足りる.

Project Euler 315

nの各桁の総和をsum(n)とする. (sum(123) = 1+2+3 = 6)
数nの右からi桁目を $n_i$ とする. $123_1 = 3, \, 123_2 = 2, \, 123_3 = 1, \, 123_4 = _$
数字dを表示するとき点灯するセグメントの本数をnum_seg(d)とする. ただし, num_seg(_) = 0とする.
数字dを数字eに変更するコスト(dとeの異なるセグメントを消灯,点灯するコスト)をc(d,e)とする.
ただし, c(d,_) = dを消灯するコスト = numseg(d)とする.

サムの方法で, 既にnが表示されている状態から始めて数字根を表示しきるまでのコストをsams(n)とすると
$sams(n) = \sum_{i=1}^{L} numseg(n_i) + numseg(sum(n)_i) + sams(sum(n))$

マックスの方法で, 既にnが表示されている状態から始めて数字根を表示しきるまでのコストをmaxs(n)とすると
$maxs(n) = \sum_{i=1}^{L} c(n_i,sum(n)_i) + maxs(sum(n))$
ただし, Lはnの桁数.

nが1桁のとき, sams(n) = maxs(n) = nを消灯するコスト = numseg(n)

区間ふるいを使ってみた.

Project Euler 329

i回目のジャンプで鳴く鳴き声をs[i]とする.
s=[P,P,P,P,N,N,P,P,P,N,P,P,N,P,N]
s.length==15

位置iにいるカエルがs[j],s[j+1],...,s[14]と鳴く確率をf(i,j)
位置iにいるカエルがs[j]と鳴く確率をp(i,j)
とすると

f(i,14) = p(i,14)
j < 14のとき

f(1,j) = p(1,j)f(2,j+1)
f(500,j) = p(500,j)f(499,j+1)

1 < j < 500, j < 14のとき

f(i,j) = (1/2)p(i,j)f(i-1,j+1)+(1/2)p(i,j)f(i+1,j+1)

p(i,j)は
(iが素数かつs[j]=P)または(iが素数でないかつs[j]=N)のときp(i,j) = 2/3
それ以外のときp(i,j) = 1/3

Project Euler 345

割当問題なのでglpkで解いてみた.
http://gusek.sourceforge.net/gusek.html:GUSEKのサンプルについていたassign.modを流用できた.

Project Euler 371

3桁の数を合計が1000になるペアに分ける. 500と000だけは特別扱いする.
ペア1: [001,999]
ペア2: [002,998]
ペア3: [003,997]
...
ペア499: [499,501]
500, 000
すると勝ちの条件は

500が二回出る
既に出ているペアの片割れが出る(例えば, 既に012が出ているときに988が出る)

Q(k,t)を, k個のペアが出て500がt回出ている状態として状態遷移の仕方を考える
Q(k,0)の状態で

000が出る →Q(k,0)
500が出る →Q(k,1)
k個のペアの片割れが出る →勝ち
k個のペアの既に出た番号が出る →Q(k,0)
上記の他の番号が出る →Q(k+1,0)

Q(k,1)の状態で

000が出る →Q(k,1)
500が出る →勝ち
k個のペアの片割れが出る →勝ち
k個のペアの既に出た番号が出る →Q(k,1)
上記の他の番号が出る →Q(k+1,1)

f(k,t)を, 状態Q(k,t)から始めて勝つまでの期待台数とする.
f(k,t) = 1+P(000が出る)f(k,t)+P(500が出る)f(k,t+1)+P(k個のペアの既に出た番号が出る)f(k,t)+P(それ以外)f(k+1,t)
f(k,2) = 0
f(499,t) = 1+P(000が出る)f(499,t)+P(500が出る)f(499,t+1)+P(499個のペアの既に出た番号が出る)f(499,t)

これをf(499,1)から順に解いていってf(0,0)の値を求める.
f(499,1) = 1/{1-P(000が出る)-P(499個のペアの既に出た番号が出る)}
f(499,0) = {1+P(500が出る)f(499,1)}/{1-P(000が出る)-P(499個のペアの既に出た番号が出る)}
f(k,1) = {1+P(それ以外)f(k+1,t)}/{1-P(000が出る)-P(k個のペアの既に出た番号が出る)}
f(k,0) = {1+P(500が出る)f(k,1)+P(それ以外)f(k+1,0)}/{1-P(000が出る)-P(k個のペアの既に出た番号が出る)}

Project Euler 381

pを5以上の素数とする.

ウィルソンの定理より
$(p-1)! = -1 mod p$
$(p-2)! = (p-1)!(p-1)^(-1) = (-1)(-1)^{-1} = 1 mod p$
$(p-3)! = (p-2)!(p-2)^(-1) = -(2^{-1}) mod p$
$(p-4)! = (p-3)!(p-3)^(-1) = (2^{-1})(3^{-1}) mod p$
$(p-5)! = (p-4)!(p-4)^(-1) = -(2^{-1})(3^{-1})(4^{-1}) = -((2^{-1})^3)(3^{-1}) mod p$

p+1は偶数だから, 2^(-1) = (p+1)/2 mod p
p = 1 mod 3のときp=3m+1と表せるから, 3^(-1) = -m = -(p-1)/3
p = 2 mod 3のときp=3m+2と表せるから, 3^(-1) = m+1 = (p+1)/3

Project Euler 387

1〜12桁のright truncatable Harshad numberのリストを作って
そこからstrong Harshad numberであるものだけ取り出して
取り出したリストからstrong, right truncatable Harshad primeを作ればよい.

n桁のright truncatable Harshad numberはn-1桁のものの右端に一桁付け加えて作る.
strong, right truncatable Harshad primeはstrong, right truncatable Harshad numberの右端に一桁の奇数を付け加えて作る.

Project Euler 419

Look and Say Sequenceの性質であるCosmological Theoremを使う.

Conwayによると, Look and Say Sequenceの第8項以降の各項は92種類の基本元素に分割できて
基本元素の変化だけで, 全部の項が生成できる.
http://www.njohnston.ca/2010/10/a-derivation-of-conways-degree-71-look-and-say-polynomial/

例えば
第8項目の1113213211は11132と13211に分割できて, これ24番と39番に対応する.
24番の11132は83番の311312
39番の13211は9番の11131221
にそれぞれ変化して
第9項目の31131211131221 = (83番)(9番)になる.
83番の311312は45番の1321131112
9番の11131221は71番の3113112211
にそれぞれ変化して
第10項目の13211311123113112211=(45番)(71番)になる.
これ以降も同様にして基本元素の変化だけで表せる.

1の個数, 2の個数, 3の個数などは各基本元素の個数さえ分かれば順番は必要ないから
24番は1個の83番に遷移する
39番は1個の9番に遷移する
といった遷移の情報を持つ92行92列の遷移行列Mを作って, $M^{10^{12}-8}v$ を計算すればよい.
ただし, vは第8項の基本元素の個数を表現したベクトルで24番と39番が1個ずつある.