プロジェクトオイラー http://projecteuler.net/index.php Q181. 3つのBと1つのWの分割を考えると、次のような7通りが考えられる。 (BBBW), (B,BBW), (B,B,BW), (B,B,B,W), (B,BB,W), (BBB,W), (BB,BW) 60のBと40のWなら何通りか。 これは二次元版の分割数と…

プロジェクトオイラー http://projecteuler.net/index.php Q179. nとn+1の約数の個数が同じ1 < n < 107の個数。 一つずつ約数の個数を求めてもいいが、それでは面白くないし、因数分解に時間がかかるので遅い。 約数の個数を格納する配列を作り、それを頭か…

プロジェクトオイラー http://projecteuler.net/index.php Q178. 45656のように隣の桁から1ずつ変わって、かつ0〜9をすべて使う1040より小さい数はいくつあるか。 一次元のランダムウォーク。場所を0〜9に限定して39回まで動かす。そのときに、0〜9をすべて…

プロジェクトオイラー http://projecteuler.net/index.php Q175. Q.169のf(n)で、f(n)/f(n-1) = 123456789/987654321になるような最小のnを与えられた記法（リンク先参照）で表せ。 あれこれ考えたが、123456789/987654321 = 13717421/109739369で、13717421…

プロジェクトオイラー http://projecteuler.net/index.php Q161. 2種類のトリオミノを9×12の格子に敷き詰める方法は何通りあるか。 最初、深さ優先探索をしたら時間的に話にならなかった。 すぐに、状態とそれが何通りあるかを記憶していけばそれなりにいけ…

プロジェクトオイラー http://projecteuler.net/index.php Q174. 前の問題で、同じタイルの枚数を並べ替えて別の形状にできることがある。これが10通り以下のタイルの枚数は100万までにいくつあるか。 タイルの枚数は、4m(n-m) (m

プロジェクトオイラー http://projecteuler.net/index.php Q173. 正方形のタイルを正方形上に並べる。ただし、中央に正方形の穴を開ける。100万個までのタイルを使ったとき、この形状は何通りできるか。 外側にn枚、m層並べたとすると、その合計枚数は、n2 -…

プロジェクトオイラー http://projecteuler.net/index.php Q172. 頭が0でない18桁の数で、同じ数字を3つより多く使っていないものの個数。 まず、18を3以下の数に分割する。それぞれの分割について対応する数を数える。例えば8を[3, 2, 2, 1]と分割すると、1…