Project Eulerのメモ - Readme sometime

Project Euler 151

A1の紙がa1枚, A2の紙がa2枚, ..., A5の紙がa5枚あるときから始めて, 封筒に紙が1枚だけ入っている回数の期待値を
$f(a_1,a_2,a_3,a_4,a_5)$ として漸化式を立てて, $f(1,0,0,0,0)$ を求める.
例えば紙の枚数が $(a_1,a_2,a_3,a_4,a_5)$ の日にA3の紙を手にとったら, 次の日の紙の枚数は $(a_1,a_2,a_3-1,a_4+1,a_5+1)$ になる.

Project Euler 158

左隣の文字より辞書順で後になる文字がちょうど1個
⇔
a,b,...,zを0,1,...,25に置き換えたとき
左隣の数より大きい数がちょうど1個
⇔
$a_1 \gt a_2 \gt \cdots \gt a_i \lt a_{i+1} \gt a_{i+2} \gt \cdots \gt a_n$
が成り立つこと
つまり

0,1,2,...,25からn個をとって
$a_1 \gt a_2 \gt \cdots \gt a_i \lt a_{i+1} \gt a_{i+2} \gt \cdots \gt a_n$ になるように2グループに分ける

仕方の数を数える.

高校の場合の数の問題に出てきそう.

Project Euler 169

2^0, ..., 2^kを2個ずつまで使ってsを作る組み合わせの個数を $f(k, s)$ として漸化式を立てて計算する.
$f(k,s) = f(k-1, s-2 \cdot 2^k) + f(k-1, s-1 \cdot 2^k) + f(k-1, s-0 \cdot 2^k)$
$f(k, s) = 0 \, (s < 0 \vee 2 \cdot (2^{k+1} - 1) < s)$