プロジェクトオイラー 問１１９

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１９「数字べき乗和」
512 という数は興味深い数である.
というのも, 各桁の和を何乗かしたものに等しくなっているからである:
5 + 1 + 2 = 8, 8³ = 512 である.
この特性を持つ他の数は例えば 614656 = 28⁴である.
この数列の第 n 項を a_n と定義し, また 2 桁以上であるとしよう.
a₂ = 512, a₁₀ = 614656 となる.
a₃₀ を求めよ.


注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。



私の回答例は以下の通りです。

def f(n):
 c = 0
 for d in xrange(2, n+2):
  for i in xrange(d, 9*d+1):
   for j in xrange(2, d+1):
    a = i**j
    t = [int(k) for k in str(a)]
    if d==len(t) and i==sum(t):
     c += 1
     if c==n: return a, i, j
    
n = 30
s, i, j = f(n)
print s,"( =", i, "**", j, ")"

小さい数値から順に各桁を和を累乗して元の数になるかチェックすると、
とても１分ルールに間に合いません。
そこで、べき乗した数値を順に用意して元の数との桁数一致と各桁和をチェックします。

１．関数f(n)
・問題の数列の第n項の値を返します。
　数列aの第1項から順にチェックして第n項を検出したときに処理を終了します。

・for d in xrange(2, n+2):
　ループ変数dは求める値の桁数です。
　取り得る値の範囲は、2桁以上で、第n項ではたかだかn+1桁です。

・for i in xrange(d, 9*d+1):
　ループ変数iは、求める値a=i**jのときのiであり、また題意によりaの桁数和でもあります。
　取り得る値の範囲はaが全桁1の数値ならばd、全桁9の数値ならば9*dなのでこの間です。

・for j in xrange(2, d+1):
　ループ変数jは求める値a=i**jのときのj、べき乗です。
　取り得る値の範囲は2乗以上なので最低2、べき乗数はたかだかaの全体桁数以内です。

・a = i**j
　t = [int(k) for k in str(a)]
　aは候補の値で、tは候補aの各桁の値リスト

・if d==len(t) and i==sum(t):
　桁数一致、かつ元の数字＝数字のべき乗の桁数和が一致するかをチェックし、
　成り立てば件数カウンタcを+1し、その件数が限度nになれば終了です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
248155780267521 ( = 63 ** 8 )

プロジェクトオイラー 問１１８

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１８「パンデジタル素数集合」
1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り,複数の集合を作ることができる.
集合 {2,5,47,89,631} は面白いことに全ての要素が素数である.
1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか?



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。



私の回答例は以下の通りです。

def h(n):
 if n<2: return 0
 if n<4: return n
 if (not n%2): return 0
 for i in xrange(3, int(n**.5)+1, 2):
  if not n%i: return 0
 return n

def f(L, Lc=[], d=0, cnt=0):
 if d==9:
  return [], cnt+1
 bk = Lc[:]
 for i in xrange(len(L)):
  Lc = bk[:]
  s = 0
  for j in L[i:]: s = s*10 + j

  if Lc and Lc[0]<s: continue
  if h(s):
   Lc.insert(0, s)
   Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
  return Lc, cnt

import itertools
L0 = [i for i in xrange(1, 10)]
v = 0
for t in itertools.permutations(L0):
 L, c = f(t)
 v += c
print "cnt:", v

1から9までの数字の順列を発生させ、その１つひとつについて、素数だけの要素に分解していきます。
ただし、その分解できた要素の順番が異なっていても１つとして数えるため、要素が昇順に並んでいるパターンだけの件数を数えます。
総当たりですが１分ルールは守れるのでよしとします。

１．関数f(n)
・リストLの要素を左から素数で区切り、累積用リストLcに格納していきます。
　dは確定した全要素の合計桁数で、cntは全素数要素のパターン数です。
　最終的に必要な値は件数だけですが、この関数を回帰呼び出しで使えるようにするために、戻り値は累積用リストLcと求める件数とします。

・回帰呼び出しなので、最初は終了条件の記述が鉄則です。
　確定した全要素の合計桁数が9ならば、1～9の数字の全部を使い切っていて、累積用リストLcに求めるパターンが格納されているので、空の累積用リストとカウンタcntを+1して戻ります。

・累積用リストLcのバックアップを取ります。
　左から1桁ずつ区切って要素を確定していく中で、区切り方が条件に合わない場合に直前状態に戻すためです。

・for j in L[i:]: s = s*10 + j
　位置iから右側を切り取り L[i:]とし、
　jのforループ中で、1けたずつ取り出して10倍しながら足していき数値化しsとします。

・if Lc and Lc[0]<s: continue
　重複を避けるため、全要素が昇順になる場合だけ採用し、それ以外は次へ。

・if h(s):
　　Lc.insert(0, s)
　　Lc, cnt = f(L[:i], Lc, d+len(L)-i, cnt)
　関数hで数値sの素数判定します。
　素数ならば、累積用リストLcに右から追加します。
　そしてリストLの位置iから左側L[:i]について、当関数fを再起呼び出しして、さらに素数の要素があるか探索します。
　 
２．関数h(n)・問１１１の素数判定を改良しました。
　2未満に素数は無く、2と3は素数。ここまではif文で直接判定します。
　その後は偶数を外し、3から先の奇数の倍数を外します。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
44680

プロジェクトオイラー 問１１７

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１７「赤タイル, 緑タイル, そして青タイル」
黒い正方形のタイルと, 
2 ユニットの長さの赤のタイル, 
3 ユニットの長さの緑のタイル, 
4 ユニットの長さの青のタイルから選んで組み合わせて, 
5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある.

長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか.

注: この問題は Problem 116 に関連する






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def e(n, m, d):
	if n not in d:
		d[n] = sum([e(n-i, m, d) for i in xrange(1, m+1)])
	return d[n]

def f(n, m):
	d = {0:0}
	for i in xrange(1, m+1): d[i] = e(i, i-1, d)+1
	return e(n, m, d)

n = 50
m = 4
s = f(n, m)
print s

4個以下の長さのブロック4種類を使って一列にタイルを敷きます。
パターン数辞書dに使うタイルの分の初期化をして求めます。

１．関数e(n, m, d):
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書（連想配列）です。
　1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
　ループ変数iが1からmまで１つずつ変化しながら、全体がn-i個の状態の直後にi個ブロックを1つ置く場合のパターン数の累積値です。

２．関数f(n, m)
・全体がn個で、m個以下のブロックからできているパターン数を返します。
・まず、パターン数辞書の初期状態を準備します。
　キー=0の場合、パターン数は0です。
・d[n] = e(i, i-1, d)+1
　0<キーi<mの場合、パターン数は全体がi個で、i-1個以下の長さのブロックからできているパターン数とi個ブロック1つだけ置くパターン数1の和です。
・ここまででパターン数辞書の初期状態が準備できたら、
　関数e(n, m, d)が求める値なので、これを求めて返します。





解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
100808458960497

プロジェクトオイラー 問１１６（別解）

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１６「赤タイル, 緑タイル, あるいは青タイル」
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える.

もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.

もし緑のタイルを選んだ場合は, 3 通りである.

もし青のタイルを選んだ場合は, 2 通りである.

複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.

50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか. 
ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.

注: この問題は Problem 117 に関連する






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def e(m, n, d):
	if n not in d:
		d[n] = e(m, n-1, d)+e(m, n-m, d)
	return d[n]

def dd(n):
	d = {0:0, n:2}
	for i in xrange(1, n): d[i] = 1
	return d

def f(n, t):
	s = 0
	for m in t:
		d = dd(m)
		s += e(m, n, d) -1
	return s

n = 50
t = 2,3,4
s = f(n, t)
print s

前回の解法は、問１１４、１１５を参考に続けて考えたため、終端のブロックが1個かm個かによって関数end1()とendm()として関数を分けていましたが、1個ブロックもm個ブロックもその後にどちらを置いてもいいので本質的に違いはありません。
そこで、
関数end1()とendm()を統合して、終端のブロック数に関係しない関数e()として別解を作成しました。

１．関数e(m, n, d)
・全体がn個で、1個とm個のブロックからできているパターン数を返します。
・dは全体がn個の場合のパターン数の辞書（連想配列）です。
　1度計算した値はこの辞書に格納して重複して計算しないようにします。
・全体がn個になる場合のパターン数は、
　全体がn-1個の後に1個ブロックを1つ置く場合と
　全体がn-m個の後にm個ブロックを1つ置く場合の２系統あるので、この和になります。

２．関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
　1個ブロックとn個ブロックの両方があることを考慮します。
・具体的には以下のとおりです。
　キー=nの場合、1個ブロックn個連続またはm個ブロック1個の場合なのでパターン数は2、
　0<キー<nの場合、1ブロックが連続しているパターンだけなのでパターン数は1、
　キー=0の場合、パターン数は0となります。

３．関数f(n, t)
・全体のブロック数nのときの求めるパターン数を返します。
　ただし、引数tは1個ブロックとともに使用するm個ブロックのmに相当する数のタプルです。
　本問では赤(長さ 2), 緑(長さ 3), 青(長さ 4)を使用するので、t=2,3,4となります。
・ループ変数mとして引数tから値を１つずつ取り出します。
・パターン数辞書をdとして、関数dd()で初期化した状態で準備します。
・mの値ごとに関数e()でパターン数を求め、
　全部1個ブロックの場合は数えないのでそのパターン数1を引きます。
・上記を使用するm個ブロックの分だけ累積します。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
20492570929

プロジェクトオイラー 問１１６

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１６「赤タイル, 緑タイル, あるいは青タイル」
5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで,この色のついた長方形のタイルでいくつか置き換える.

もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある.

もし緑のタイルを選んだ場合は, 3 通りである.

もし青のタイルを選んだ場合は, 2 通りである.

複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある.

50 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は何通りあるか. 
ただし複数の色を混ぜることはできず, 少なくとも 1 個は色のついたタイルを使うこと.

注: この問題は Problem 117 に関連する






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def end1(m, n, d1, dm):
	if n not in d1:
		d1[n] = end1(m, n-1, d1, dm)+endm(m, n-1, d1, dm)
	return d1[n]

def endm(m, n, d1, dm):
	if n not in dm:
		dm[n] = end1(m, n-m, d1, dm)+endm(m, n-m, d1, dm)
	return dm[n]

def dd(n):
	d = {n:1}
	for i in xrange(n): d[i] = 0
	return d

def f(n, t):
	s = 0
	for m in t:
		d1, dm = dd(1), dd(m)
		s += end1(m, n, d1, dm) + endm(m, n, d1, dm) -1
	return s

n = 50
t = 2,3,4
s = f(n, t)
print s

問１１４、１１５との違いは以下です。
a.m個ブロックも1個ブロックと同様に連続してよい。
b.最低1つは色ブロックが必要。つまり、全部黒1個のパターンは数えない。
c.黒1個ブロックの他に3色あり、3色は混ぜられない。

そこで、問１１５で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()と
同終端が赤ブロックの関数endr()に基づいて、それぞれ、
全体がn個で終端が1個ブロックのパターン数を関数end1()と
同終端がm個ブロックの関数endm()として調整します。

上記aの対応で、endm()は全体個数がn-m個のときのend1()とendm()の和になります。
上記bの対応で、f()では全部が1個ブロックの場合の1パターン分、減らします。
上記cの対応で、3色別々に計算し、合計します。

１．関数end1(m, n, d1, dm)
・全体がn個で、1個とm個のブロックからできていて末尾が1個ブロックのパターン数を返します。
・問１１５の関数endb()の変数名を変更しただけでまったく同じ関数です。
・d1は終端が1個ブロックで全体がn個の場合のパターン数の辞書（連想配列）です。
　dmは終端がm個ブロックで全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に1個ブロックを置いて全体がn個になる場合のパターン数は、
　全体がn-1個で終端が1個ブロック、m個ブロックのときのパターン数の和になります。

２．関数endm(m, n, d1, dm)
・全体がn個で、1個とm個のブロックからできていて末尾がm個ブロックのパターン数を返します。
・d1、dmは関数end1のときと同様です。
・終端にm個ブロックを置いて全体がn個になる場合のパターン数は、
　全体がn-m個で終端が1個ブロック、m個ブロックのときのパターン数の和になります。

３．関数dd(n)
・n個ブロックを使用する場合のパターン数辞書の初期状態を返します。
　具体的には、キー=nの値が1で、キー<nの値が0である辞書（連想配列）を返します。

４．関数f(n, t)
・全体のブロック数nのときの求めるパターン数を返します。
　ただし、引数tは1個ブロックとともに使用するm個ブロックのmに相当する数のタプルです。
　本問では赤(長さ 2), 緑(長さ 3), 青(長さ 4)を使用するので、t=2,3,4となります。
・ループ変数mとして引数tから値を１つずつ取り出します。
・d1、dmとして、終端が1個ブロックとm個ブロックのパターン数辞書を
　関数dd()で初期化した状態で準備します。
・mの値ごとに、終端が1個ブロックの場合と終端がm個ブロックの場合の、
　それぞれのパターン数を関数end1()、関数endm()で求めて合計し、
　全部1個ブロックの場合は数えないのでそのパターン数1を引きます。
・上記を使用するm個ブロックの分だけ累積します。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
20492570929

プロジェクトオイラー 問１１５

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１５「ブロックの組み合わせ方の数え上げ その2」
注意: これは Problem 114 をより難しくした問題である.

長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい).

敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする.
例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である.
m = 3 の時, n = 30 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
同様に, m = 10 では F(10, 56) = 880711, F(10, 57) = 1148904 であることがわかり, つまり n = 57 がこの敷き詰め計数関数が初めて 1,000,000 を超える最小の値であることがわかる.
m = 50 のとき, この敷き詰め計数関数が初めて 1,000,000 を超える最小の n の値を求めよ.






注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def endb(m, n, bd, rd):
	if n not in bd:
		bd[n] = endb(m, n-1, bd, rd) + endr(m, n-1, bd, rd)
	return bd[n]

def endr(m, n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(m, i,bd,rd) for i in xrange(n-m+1)])
	return rd[n]

def f(m, k):
	bd = {0:0, 1:1}
	rd = {m:1}
	for i in xrange(m): rd[i] = 0

	n = 0
	while endb(m, n, bd, rd)+endr(m, n, bd, rd)<=k: n += 1
	return n


m=50
k = 1000000
n = f(m, k)
print n

問１１４との違いは、以下の２点です。
a.赤ブロックの最小個数が3個固定だったのがm個になったこと。
b.全体の長さを固定にしてパターン数を求めていたことに対して
　パターン数の下限値から全体の長さの最小値を求めること。

そこで、問１１４で作成した、
全体がn個で終端が黒ブロックのパターン数の関数endb()、
同赤ブロックの関数endr()を上記aに対応できるように改良し、
求める値を返すf()も上記bに合わせて改良します。

１．関数endb(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が黒ブロックのパターン数を返します。
・問１１４の関数endb()に引数mを追加し、呼び出す関数endr()も問１１４のものに引数mを追加するので、それに合わせました。
・bdは終端が黒で全体がn個の場合のパターン数の辞書（連想配列）です。
　rdは終端が赤で全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
　全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

２．関数endr(m, n, bd, rd)
・赤ブロックが最小m個、全体がn個で終端が赤ブロックのパターン数を返します。
・問１１４の関数endb()に引数mを追加し、固定値2の部分をm-1に改良しました。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の２つの場合があります。
　a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
　b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
　　この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

　aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
　bの場合はループ変数iを0からnのm個手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

３．関数f(m, k)
・赤ブロックの最小個数mで問題の条件に合うパターン数が下限値k個を超える、全体の長さの最小値を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さが、黒は1個で、赤はm個なので、黒赤それぞれでその値未満のパターン数は0で、その値で1パターンが初期値になります。
　なお、辞書rdには、キーmのとき1を固定で設定し、m未満のキーのときはfor文で回して0を設定します。
・黒赤それぞれのが終端となるパターン数の和が全パターン数です。
　全体の長さnは0から始めて1ずつ増加させながら全パターン数を計算していき、
　この全パターン数が下限値kを超えたら、そのときのnを返します。



解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
168

プロジェクトオイラー 問１１４

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１１４「ブロックの組み合わせ方の数え上げ その1」
長さ 7 ユニットからなる 1 列上に, 最低 3 ユニットの長さを持つ赤ブロックが置かれている. 
ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). 
これを敷き詰める方法は, ちょうど 17 通りある.

50 ユニットの長さの 1 列を敷き詰める方法は何通りあるか.

注意: 上の例では起こりえないが, 通常はブロックの大きさが複数混ざっていてもよい. 
例えば, 8 ユニットの長さの 1 列では, 赤(3), 黒(1), 赤(4) を使うことができる.







注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の回答例は以下の通りです。

def endb(n, bd, rd):
	if n not in bd:
		bd[n] = endb(n-1, bd, rd) + endr(n-1, bd, rd)
	return bd[n]

def endr(n, bd, rd):
	if n not in rd:
		rd[n] = 1 + sum([endb(i,bd,rd) for i in xrange(n-2)])
	return rd[n]

def f(n):
	bd, rd = {0:0, 1:1}, {0:0, 1:0, 2:0, 3:1}
	return endb(n, bd, rd) + endr(n, bd, rd)

n=50
s = f(n)
print s

黒ブロック（長さ１個）または赤ブロック（長さ３個以上）を１つずつ置いていって個数を数えます。
ただし、赤ブロックは連続では置けないので、
順番に並べていく中で終端が赤か黒かで別々の関数にします。

１．関数endb(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bdは終端が黒で全体がn個の場合のパターン数の辞書（連想配列）です。
　rdは終端が赤で全体がn個の場合のパターン数の辞書（連想配列）です。
　いずれも1度計算した値はこれらの辞書に格納して重複して計算しないようにします。
・終端に黒ブロックを置いて全体がn個になる場合、
　全体がn-1個で終端が赤でも黒でも置けるので、これらのパターン数の和になります。

２．関数endr(n, bd, rd)
・全体がn個で終端が黒ブロックのパターン数を返します。
・bd、rdは関数endbのときと同様です。
・終端に赤ブロックを置いて全体がn個になる場合は以下の２つの場合があります。
　a.まだ何も置いていなくて長さn個の赤ブロックを置く場合
　b.端が黒でn個まで2個以上のすきまがあり、すきまの長さ+1個の赤ブロックを置く場合
　　この場合、置く直前のブロックは黒ブロックの場合だけなのでendb関数を呼び出します。

　aの場合は1パターンなので赤辞書rdのキーnの初期値に1として設定します。
　bの場合はループ変数iを0からnの3つ手前まで回して、長さiの黒ブロックで終わって長さn-iの赤ブロックを1つ置くパターン数を足します。

３．関数f(n)
・問題の条件で長さnで1列を敷き詰めるパターン数を返します。
・bd、rdは関数endbのときと同様です。
　最小の長さは黒が1個で赤が3個なので、黒赤それぞれでこの値未満のパターン数は0で、その値で1パターンというのが初期値になります。
・黒赤それぞれのが終端となるパターン数の和が、求めるパターン数です。

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
16475640049