Project Euler

■088
長さnの数列(a_k)を作る．
但し，任意のkについて，
2≦a_k<a_k+1
この時，
Σ=Σ_k a_k
Π=Π_k a_k
と置き，
1+…+1+Σ=1*…*1*Π
が成り立つとすれば，1の個数mは
m=Π-Σ
となる．
よって，総和(総積)がΠであり長さがn+mの数列が出来たことになる．
Σ,Πは再帰で生成するが，再帰回数nは12000程度で十分である(と思う，それ以上の長さを生成しても意味が無いから)．
min[len]=条件を満たす長さlenの数列の総和(総積)の最小値
として，minを更新していく．

■098
それぞれの文字列をASCIIでソート．ソートした後の文字列群で等しいものがアナグラム対となる．アナグラム対(s, t)に対して，桁数がsの長さである自乗数を全て生成する．sとある自乗数mを対応させ，アルファベット->数字のマッピングを作る．条件を満たさない(違うアルファベットに同じ数字が割り当てられる等)マッピングになるときはそこで終了する．マッピングを用いてtに対応する数値nを生成．nが自乗数ならすべての条件を満たしたことになる．
これらを満たすもののうち，最大のものを見つければ良い．

■151
[仕事の回数][A1の枚数][A2の枚数][A3の枚数][A4の枚数][A5の枚数]=その組み合わせが起こる確率
でDP．
考えられる組み合わせ全てについて，
dp[k][b1][b2][b3][b4][b5]+=dp[k-1][a1][a2][a3][a4][a5]*ak/(a1+a2+a3+a4+a5)
で更新．akを引いたとし，その後のそれぞれの紙の枚数をb1,b2,b3,b4,b5とする．
例えば，a3を引いたとしたら，
b1=a1
b2=a2
b3=a3-1
b4=a4+1
b5=a5+1
となる．

これで，ついに150問に到達し，Level 4となりました．

Project Euler

■110
x=n+k
と置くと，
y=n²/k+n
となる．kはn²を割り切る必要があるため，重複を含めてn²の約数の数だけ解があることが分かる．
n=2^r₁3^r₂5^r₃…
のように素因数分解出来たとき，n²の約数の数cは，
c=(2r₁+1)(2r₂+1)(2r₃+1)…
となる．
cが8000000(重複しているので2倍)を超えるような最小のnを探索で見つける．

■135
x=a+2d,y=a+d,z=a
と置くと，
(-a+3d)(a+d)=n
となり，
n=pq
とすれば，
d=(p+q)/4
a=(-p+3q)/4
となる．nについて，a,dがそれぞれ自然数となるような(p,q)の個数が解の個数となる．

■136
135を流用．非常に時間がかかった．

■139
a<b<cとすると，小正方形の面積は，
c²-2ab=(a-b)²
なので，小正方形の辺の長さmは，
m=(b-a)
つまり(b-a)|cであるものを数えれば良い．
ピタゴラス数生成行列で探索するだけ．

Project Euler

■086
3辺をx<y<zとすると，
最短距離は
√[(x+y)²+z²]
となる．
a<b<cであるピタゴラス数
a²+b²=c²
と対比させると，
a=x+y, b=z, c=最短距離
または，
a=z, b=x+y, c=最短距離
と書ける．
ピタゴラス数(a, b, c)を適当に生成した時，前者・後者の組み合わせ数をそれぞれ以下のようになる．
・前者
1辺の最長はbで，b≦Mの時，x/2個．
・後者
1辺の最長はaで，a≦Mの時，max{(2x-y+2)/2, 0}個．

■131
実験的解法になってしまったので省略．

Project Euler

■215
可能なレンガの組み合わせをDFSか何かで予め求めbitで表現しておく．
|---|--|--|--|
ならば，000100100100とする(端は含まない)．
[段数][組み合わせの番号]でDP．
i番目の組み合わせとj番目の組み合わせとが伝播亀裂していないならば，
dp[k][j]+=dp[k-1][i]
i番目の組み合わせのbit表現をbits[i]とすると，上の条件式は，
if((bits[i]&bits[j])==0)
と書ける．
intで処理しようとしたため，オーバーフローしていた事に気が付かなかった．

■178
[桁数][0~9のどれが出現したか][一番最下桁]でbitDP．
dp[0][1<<i][i]=1
を初期条件とし，以下の式で更新．
dp[k][j|(1<<(i-1))][i-1]+=dp[k-1][j][i]
dp[k][j|(1<<(i+1))][i+1]+=dp[k-1][j][i]

■190
ラグランジュの未定乗数法を使う．
f=Π_k x_k^k
g=Σ_k x_k-m=0
δ/δx_k (f-λg)=0
δ/δλ (f-λg)=0
結果，
x_k=2k/(m+1)
となる．あとは計算するだけ．

■207
数式を適当に弄ると，
2^t=[1+√(1+4k)]/2
となる．ここで，1+4kは奇数であるため，1+4kが平方数となるならば，
1+4k=(2a+1)²
と書くことができ，これを解くと，
2^t=a+1
k=a²+a
となる(a≧1)．
となる．
a+1が2のベキ乗である時，完全な分割となるため，aを決定したとき，完全な分割であるものの割合は，
log₂(a+1)/a²+a
となる．

■197
恐らく収束するだろうと見込みのもと適当なnまで値を見たところ，周期2の周期解に収束していた．よって，n=10¹²まで計算する必要はなく，適当なところで打ち切れば正確な答えが出る．

■159
dp[i]=iのMDRS
a[i]=iのDR
とすれば，
dp[n]=max{a[i]+dp[n/i]}
となる(iはnの約数)．
但し，
a[1]=0
dp[1]=0
としておく．

Project Euler

■094
疑正三角形は，(a,a,a+1)又は(a,a+1,a+1)となる．
前者の面積は，
S=(a+1)/4√[(a-1)(3a+1)]
後者については，
S=a/4√[(a+2)(3a+2)]
となるので，根号の中身が平方数になるものを逐一数えていけば良い．

■095
真の約数の和を事前に求めておく．ある数aについて約数の和を再帰的に求めていき循環するかどうかを調べる．

■231
20000000までの素数を列挙しておけば，素因数分解(O(√n))を(おそらく)高速化できる．
150000001~20000000までの数の素因数の出現頻度から，1~50000000までの数の素因数の出現頻度を引き，和を計算する．

■235
s(5000)が容易に発散してしまうため，事前に範囲を狭めておいてから二分探索．doubleでも十分計算可能．閉じた式は使う必要無し．

■265
ビット演算を少し使って，DFSするだけ．

Project Euler

■090
組み合わせが少ない(₉C₆²)ので全探索．9,6は区別するにも関わらず，勘定の際にはひっくり返しても良い，というややこしさがあるので注意．

■093
考えられる数式を全部試した．つまり，1,2,3,4,+,-,*,/を適当に並び替えたものを逆ポーランド記法と解釈し，(可能なものについて)構文解析する．実際には，括弧の付け方が限られるので，式の構造を決め打ちにしたほうが楽．途中計算が分数になっても良いという事に気付かなかった．a,b,c,dは，適当に4重ループを回して，適当に打ち切った時の再良解とした．

Project Euler

■051
実装が少し面倒だったがやるだけ．複数の桁を同じ数で置き換えると8つ以上の素数が出てくるので，0,1,2のどれかが2回以上出現した時のみ検査を入れる．

■066
ペル方程式の解法を実装．
http://www004.upp.so-net.ne.jp/s_honma/pell/pell.htm

Project Euler

■162
[桁数][0,1,Aの各々を1つ以上含んでいるか]でDP．
初期値は以下．
dp[1][1<<1]=1…1桁で1を含む
dp[1][1<<2]=1…1桁でAを含む
dp[1][0]=13…1桁で0,1,Aを除いた13個
最下位に0,1,…E,Fを付加していく形の更新式を作る．
dp[桁数][(1<<3)-1]が答え．
オーバーフローするので，BigIntegerで手抜きした．

■075
ピタゴラス数生成行列を使用．↓参照．
http://www.sci.hyogo-u.ac.jp/matsuyam/undergrad/gakubu07.htm
これを使うと，原始的ピタゴラス数p=[a,b,c]^tから，3つの原始的ピタゴラス数q_k=1,2,3=[a_k,b_k,c_k]^tを生成出来る．また，a+b+c<a_k+b_k+c_kであることは容易に分かる．よって，a+b+c>Lとなるpで枝刈りを行うBFSをすれば良い．

■204
やるだけ．100未満の素数を先に生成し，そこから重複無く効率良く値を計算していく．

■100
青の円盤の枚数をa，赤の円盤の枚数をbとすると，
a/(a+b) * (a-1)/(a+b-1) = 1/2
が成り立つ．
これをaについて解くと，
a=[2b+1±√(8b²+1)]/2
となる．
2b+1<√(8b²+1)
かつ，
a>0であるため，
a=[2b+1+√(8b²+1)]/2
と一意に定まる．
aは自然数であるため，判別式の値8b²+1は平方数で無くてはならない．
8b²+1=k²
とし，これを整理すると，
k²-8b²=1
という形のペル方程式になる．
この最小解は，問題文より，b=1の時であるため，
k=3であると容易に分かる．

ペル方程式について以下が成り立つ．
x-Dy²=±1
について自明でない最小解を(x, y)とする．
α=x+√Dy
に対して，
αⁿ=x_n+√Dy_n
とすると，(x_n, y_n)もまた上記方程式の解となる．

このため，α=3+√8とおき，
αⁿ=k_n+b_n√8
を計算し，そこからa_nを算出．
aⁿ+bⁿ>10¹²となれば終了．そうでなければ，nを1ずつ増加させていく．

Project Euler

■078
蟻本にあったDPを組んで，条件を満たしそうな値まで力づくで計算．

■174
173の流用．愚直にやるとO(n^2)で終わらない．

■188
オイラーの定理
a^φ(n)≡1 (mod n)
a=1777は素数であり，
n=100000000で，φ(n)=40000000
となる．
指数の一番上の方から再帰的に適用していく．
意外と時間がかかるので，指数が変わらなくなった時点で計算を打ち切った．

Project Euler

■054
実装ゲー．条件に忠実に組む．
5枚のカードのマークが全て同じかどうかと，どの数字が何枚あるかを先に計算しておくと(少し)楽．

■172 4進数でビットDP
[桁数][どの数字が何回出たか]
でDP．各数字は0~3回までしか出ないので，dp[18][4¹⁰]とすれば良い．
更新式は頑張る．

■173
全体の大きさをnとすると，最大の穴の大きさはn-2．
よって，使えるタイル数をmaxとすると，nが満たす条件は，
n²-(n-2)²≦max
となる．
最小の穴の大きさをkとすると，
n²-k²≦max
を満たすので，その最小値
k=ceil(√n²-max)
となる．但し，laminaeは上下左右に対称なので，n≡k mod 2を満たすようにkを補正．
n²-max<0
の場合は，k=0とすれば良い．
最後に，k,k+2,k+4,…,n-4,n-2の個数cは，
c=(n-2-k)/2+1
となる．
結構値が大きいため，intで計算したらオーバーフローした．注意注意…．

■183
P=(N/k)kが最大となるkを見つける．おそらく上に凸な関数なので，三分探索でも良いが，kの値の範囲は高々Nなので，単純なループでも十分可能．また，(N/k)kを正直に計算すると，doubleでもオーバーフローするので，対数をとった値k*log(N/k)を計算．
(N/k)kが無限小数になるかどうかは，N/kが無限小数になるかどうかを確かめれば良い．そのためには，まずN/kを約分しN/k=n/dとする(各々をgcd(N,k)で割る)．
d=2^a5^bと表す事が出来れば，有限小数，そうでなければ，無限小数．

Project Euler

■142
明らかに，計算量を減らす必要がある．
x+y=a²
x-y=b²
x+z=c²
x-z=d²
とする．
x=(a²+b²)/2
y=(a²-b²)/2
より，aとbを適当に決めることでxとyを決定できる．
次に，dを適当に決める．
c2=2x-d²
z=(c2-d²)/2
とすれば，
z<yかつc2が平方数である事を確認する事で，条件を満たすかどうかを判定できる．

■144
実装ゲー．
まず，直線と楕円の交点の方程式を解く．
次に，傾きaの直線が傾きmの接線によってどう反射すれば良いかを考える．
要するに，θ=tan^-1(m)だけ逆回転→y軸対称に反転→θ回転でよい．
元の光線のベクトルをv=(1, a)する．反射した光線のベクトルをuとすれば，
u=R(θ)SR^-1(θ)v
R(θ)は回転行列，Sはy軸対称に反転させる行列．
後は，適当に問題の条件を実装．ビジュアライザを作るのがオススメ．

■149
最大値の計算は全ての縦横斜めについて行う．
a[0],…,a[n-1]の部分総和の最大値の求め方．
dp[k]をa[0],…,a[k]までの部分総和の最大値とすると，
dp[k+1]=max{a[k+1], dp[k]+a[k+1]}
となる．

■150
愚直に計算するとO(n³)だが，n=1000なので現実的時間内に求められる．強いてい言うなら，横方向の総和を先にメモ化しておくと良い．
sum[n]=Σ_0≦k≦na[k]
↑こんな感じ．
a[i]+…+a[j]はsum[j]-sum[i-1]で求められる(i=0の時は単純にsum[j])．

■164
dp[桁数][上から1桁目][上から2桁目]=条件を満たす数字の個数
でDP．
初期値は，
dp[0][0][0]=1
更新式は，
i+j+k≦9なるi,j,kについて，
dp[d+1][j][i]+=dp[d][k][j]

■179
約数の数はO(√n)で求められるので，計算量はO(n√n)だが，nの最大値が10⁷と小さいので，特に工夫せず求めた．

■191
条件が変なDP．
・前日=出席，遅刻無
・前々日=出席，前日=欠席，遅刻無
・前々日=欠席，前日=欠席，遅刻無
・前日=出席，遅刻有
・前々日=出席，前日=欠席，遅刻有
・前々日=欠席，前日=欠席，遅刻有
の6変数を用いる．更新式が少し複雑になるので注意．

Project Euler

■118
再帰で全順列を生成し，その順列を適当に分割して条件を満たすか判定するだけ．簡単な枝刈りを入れれば高速．

■120
(a-1)ⁿ+(a+1)ⁿ mod a²
は結局，
2|n:
⇒2
o.w.:
⇒2an mod a²
になる．
また，2an mod a²の周期は(多分)高々aなので，計算量は一気に減る．というわけで，全探索で間に合う．

■121
[ターン数][青の個数]でDP
初期条件は，[0][0]=1．
jターン目に青(赤)を引く確率をP_青(赤)(j)とすると，
P_青(j)=1/(j+1)
P_赤(j)=j/(j+1)
となり，更新式は，
dp[j][0]=dp[j-1][0]*P_青(j)
dp[j][i]=dp[j-1][i-1]*P_青(j)+dp[j-1][i]*P_赤(j) (i>0)

■123
120のaが素数バージョン．エラトステネスの篩で適当に素数を生成しておく．

Project Euler

問題文は，リンクのProject EulerやProject Euler - PukiWikiを参照して下さい．

■101
(x_i, y_i)の対から，多項式の係数を求める公式があった気がするけど忘れてしまったので，
Ax=y
の形の方程式に変形して(掃き出し法で)解いた．
y_i=f(x_i)=Σ_0≦k≦na_kx_i^k
とした時，A_{j, i}は(j+1)ⁱ，x_j=a_j，y_j=f(x_j)となる(Aとyが既知)．

■102
外積で簡単に解ける．
原点をO，3頂点をA，B，Cとする．この時，
OA×OB，OB×OC，OC×OAの符号が全て一致⇔三角形ABCは原点Oを含む．
(適当な図について，A×B=|A||B|sinθを考えれば分かる)

■104
下9桁と上15桁程度を保存しておき，そこだけを更新し逐一判定．

■113
[桁数][一番左の数字]=増加数or減少数の個数でDP．
初期条件は，
増加数[0][9]=1，減少数[0][0]=1
上で求めた値の和から，増加数かつ減少数の個数を引けば良い．

Project Euler

problem 107
最小全域木．終了．

problem 205
[1,4]の四面体サイコロ9つと，[1,6]の立方体サイコロ6つでゲームを行う．それぞれの合計値を比較し，大きい方が勝ちとする．前者が勝つ確率は幾らか．
それぞれについて，0~36がそれぞれ何回出現するか数えて比較するだけ．

100問解いたので，やっとこさLevel 3になりました．

Project Euler

problem 59
XORにより暗号化された文から平文を推測する問題．かなり適当に解いた．

problem 89
与えられたローマ数字を最小文字数で表す問題．文字の先読みをして適当に解く．

Project Euler

problem 70
1<n<10において，10進数で表したφ(n)がnの並び替えになっているものの内，n/φ(n)が最大となるnを求めよ，という問題．
φ(n)の計算が予想以上に遅く，苦戦．最後はマシンパワーに頼った．

problem 80
1≦n≦100において，√n(ただし√nは無理数)の上位100桁をそれぞれ足しあわせた合計を求めよ，という問題．
BigDecimalの精度をMathContext.UNLIMITED(無制限)に設定し，愚直なループで√nを求めた．

Project Euler

problem 72
problem 73

Project Euler

problem 71
problem 79

Project Euler

problem 61
problem 76
problem 77

Project Euler

problem 91
problem 119
problem 203