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
としておく．