Euler85 & Euler159

またまたProject Euler
これで97問正解

Problem 159

問題150と同様に動的計画法で解けます。
問題150よりも簡単。

Problem 85

長方形の内部に部分長方形(正方形含む)の個数を数える問題です。
と思ったら打ち間違えた、問題を解く上で数え上げの部分の印象が強かったから間違えてたｗ。
部分長方形が2000000個に限りなく近い長方形の面積を答える問題でした。


長方形のサイズが2*3(H,W)のとき、部分長方形1*2(h,w)の個数は
(2-1+1) * (3-2+1) = 4
(H-h+1) * (W-w+1)
で得ることが出来る。
縦を1に固定すると、
(2-1+1) * { (3-1+1) + (3-2+1) + (3-3+1) }
この式で縦1のときの部分長方形の個数が全て得られる。
(3-1+1) + (3-2+1) + (3-3+1) = W^2-W(W+1)/2+W = W(W+1)/2
上記の式はこのように変形させることが出来る。
W(W+1)/2 = Bと置いて、縦も列挙していくと
(2-1+1)*B + (2-2+1)*B = { (2-1+1)+(2-2+1) } * B
縦も同様に、
H(H+1)/2 に変形させて、Aと置くと、 A*B = H(H+1)/2 * W(W+1)/2
という式になる。
これで部分長方形の個数を得ることが出来る。
あとは長方形の大きさを2重ループで変形させて探索。
部分長方形の個数を得る式が自然数の和の公式の掛け算になることにびっくりした。
でもよく考えればその通りで、問題を見た瞬間に出来なかったことが悔しい。
ある部分を固定して列挙したとき、違うものが見えてくることがある…覚えておこう。