Project Euler 173
使うタイルの枚数をn, laminaeの輪郭の正方形の一辺の長さをa, 穴の正方形の長さをb とする.
100以下を考えるとすると
b= 1のとき(穴が1*1マスのとき)
a = 3, n = a**2 - b**2 =3**2 - 1**2 = 8
a = 5, n = 5**2 - 1**2 = 24
a = 7 ,n = 7**2 - 1**2 = 48
a = 9, n = 9**2 - 1**2 = 80
a = 11,n = 11**2 -1**2 = 120(これはnが100を超えているのでダメ)
こういうふうに考えていくとa**2 - b**2 <= 100(使えるタイルの枚数は100を超えない)というループ条件が見えてくる.
続いてb = 2のとき(穴が2*2マスのとき)
a = 5, n = 5**2 - 2**2 = 21
……
b に対して最も小さいa はa = b+2 であることが分かる. 絵を描けばわかる.
というようにb を回していき条件a**2 - b**2 <= 100を満たすものだけを考えれば良い.
bをどこまで回すかについては画像のように色をつけた部分がn/4なのでそれから1ひいいたn/4-1まで回せば十分なようです.
問題ではn = 1000000です.
時間は10秒くらいでした.