Y箱

長方形を正方格子で切ったときに内部にできる長方形の数が二百万にもっとも近いものを求める問題です。

これも自分で解いたぞ。




まず、ある長方形の中の長方形の数のもとめかた。
例題の長方形(3x2)で解説。
1x1の長方形を数えてると、6こあります。このとき右下の頂点に注目すると、左辺と上辺にある点以外の数と同じであることが分ります。頂点の数は、3x2=6個です。
2x1の長方形でも同様です。このときは、初めの位置が右にずれるので1つ減って、2x2=4個です。
このように、3x2の長方形に入る長方形の個数は、結局、以下の積の和ということになります。
 3x2 2x2 1x2
 2x2 1x2
 1x1
とまあ、このようになります。
システマチックなので、計算は簡単ですね。

さて、問題は、この結果が二百万に最も近いものを求めるわけですが、この、「一番近い」ってのがクセモノです。実際、100x100までの全ての長方形の場合を数えるのにたいして時間はからりません。
このときの計算は、
1x1 1x2 1x3 ....  1x100
2x2 2x3 ......  2x100
のように進めていくわけで、この「100」が無いと、計算が進められない。でも、この100にはなんの根拠もないわけで、うまくない。
で、違うほうほうをひねり出した。


長方形のうち、二百万に近いものたちは、辺の長さの和も近いんじゃないかと仮定しました。

正方形で初めて二百万を超えるものから始めて、辺の長さを増減して、差の小さいものをみつけます。

手続きはこんな感じ。

• 1から始めて、中の長方形の数を数え、初めて二百万を超えるものをみつける
• 二百万を超えていたら、右の辺の長さを1減らす。減らせなければ、終り
• 二百万以下だったら、左の辺の長さを1増やす。

です。
増減で別の辺を使うところがミソ。

このように作ったのが以下の処理。

count-rectargle

n x mの長方形の中にある長方形の数を出す。書いたとおりのやりかた。

pe85