1. 問題
 様々なサイズの長方形(または正方形)の紙Aが与えられている。1枚の紙Aを、折り紙するための4枚の正方形Bに切り分けたいけど、もっとも大きな折り紙Bが得られるような、最適なAがどれかを選べ。

2. 実例
 以下の実例を見てみる。

3 ← 与えられる紙の数
10 20 ← 1枚目の紙 10 x 20
40 8 ← 2枚目の紙 40 x 8
12 12 ← 3枚目の紙 12 x 12 の正方形
0 ← 入力データの終了

1枚目の紙10×20では最大5×5の折り紙しか得られない。2枚目の紙40×8では最大8×8の折り紙が得られる。3枚目の紙12×12では最大6×6の折り紙しか得られない。ということで、2枚目の紙を選べば、最大サイズの折り紙を手にすることができるわけだ。

3. 計算法
 縦幅に比べ、横幅の短くない長方形(または正方形。そうでなければ90°回転すればOK)に対して、最大サイズの折り紙(正方形、同一サイズ)4枚は3通りの並び方にしかならない。

p11207.jpg

長方形の縦幅サイズをY、横幅サイズをXとすると、3パターンによって得られる折り紙の最大サイズはそれぞれ、

 パターン1: X/4 と Y の小さいほうの値
 パターン2: X/2 と Y/2 の小さいほうの値
 パターン3: X/3 と Y/2 の小さいほうの値

になる。3パターンに対応する3つのサイズから、最大サイズを得、それが長方形 X, Y に対して入手できる折り紙の最大サイズになる。

さらに、与えられたすべての紙の中から、最大サイズのものをピックアップすれば、答えが得られる。

ということで、本問題は簡単に解ける。残りは実行時間の短縮ということだ。

自分の書いたプログラムは最初0.020秒だったけど、最適化を施し、最終的に0.000秒に到達した。つまり、乗算、除算しないで、ビットシフトでの計算を心がけた。

例えば、元のサイズX, Y を最初から12倍すれば、2, 3, 4で割り切れるので、実数ではなく、整数だけで計算可能になる。

となると、3つのパターンはそれぞれ

 パターン1: min(3X, 12Y)
 パターン2: min(6X, 6Y)
 パターン3: min(4X, 6Y)

に変わり、ビットシフトの性質を考えて、

 3X = (X << 1) + X  4X = X << 2  6X = 3X << 1
 3Y = (Y << 1) + Y  12Y = 3Y << 2

などと工夫すれば、除算も乗算も必要なくなる。

まあ、そんなテクニックは実行スピードの本質的な改善に繋がらないから、分からなくても構わないが、少しでも他人よりもランクを上げたい気持ちがあれば、覚えて損することはないだろう。

Comments are closed.

Post Navigation