読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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まで回せば十分なようです.

f:id:umashika5555:20161023174148p:plain

 

問題ではn = 1000000です.

時間は10秒くらいでした.

gist.github.com