Problem 115

m=3のとき

red(5)black(2)red(3) (n=10)を次のように考える

■○○□○■(□)

black(3)red(3)black(1)red(6)black(1) (n=14)ならば

○○○■□■○○○□(○)

○:直前と同じ色(先頭ならblack)

■:red のはじまり(○ (3=m)個ぶん)

□:black のはじまり (直前が red の終わり)

最後は必ずblackで終わるように列を1つ伸ばす

よってたくさんある○◇をならべて◇を先頭から交互に■と□にすると、ブロックのならびが得られる。

○=x個、◇=2y個とすると

n=x+y+y*m-1の列ができる。

import Data.List
choose n r = div (product [n-r+1..n]) $ product [1..r]
measure m n = sum [(n+1-a*(m-1)) `choose` (2*a) | a<-[..div (n+1) (m+1)]]
main = print.findIndex (>10^6).map (measure 50) $ [..]
More Reading
Newer// Problem 114
Older// Problem 116