CodeIQ 挑戦の記録 : 第81回「今週のアルゴリズム：長方形から作る正方形」

CodeIQというサイトで問題に挑戦した記録です。

codeiq.jp

問題文を要約すると、

  • 標準入力から整数m,nが与えられる。
  • 長辺がmの長方形から(短辺の長さx短辺の長さの）正方形を切り取り、残った長方形から更に正方形を切り取るという 事を長方形が無くなるまで繰り返す。
  • この時、できた正方形の数を数えるが、長辺がm以下の長方形で正方形がn個できるものの縦・横のパターンが何通りあるか解答する。
  • \( m \le 1000 \)

方針

動的計画法を用いる。
{i \times j} \((i<j)\) の大きさの長方形から切り取る事ができる正方形の個数を{f(i,j)}とすると、漸化式は下記の通り

{ f(1,j)=j }
{ f(i,j)= floor( j \div i ) + f(( j \% i ), i) }   \( (i<j) \)

漸化式の説明

  • {1\times j}の大きさの長方形には 1\times 1 の大きさの正方形が{j} 個含まれる。
  • {i\times j}の大きさの長方形\((i<j)\)には{i\times i}の大きさの正方形が{j\div i}個と、これらの正方形を取り除いた{i\times (j \% i)}の長方形が残るが、これは縦・横を入れ替えた大きさのものを計算済みであるのでその結果を利用する。

f:id:ibeckuu:20160223223623j:plain
(1,j)
{1 \times 1}の大きさの正方形が{j}個

f:id:ibeckuu:20160223223801j:plain
(2,j)
{2 \times 2}の大きさの正方形が{j\div 2}個
\(+\) \( 2 \times (j \% 2)\)の大きさの長方形（＝正方形の個数は既に\((j \% 2,2)\)に代入されているのでこれを参照する）

f:id:ibeckuu:20160223231056j:plain
(3,j)
{3 \times 3}の大きさの正方形が{j\div 3}個
\(+\) \( 3 \times (j \% 3)\)の大きさの長方形（＝正方形の個数は既に\((j \%3,3)\)に代入されているのでこれを参照する）

f:id:ibeckuu:20160224005645j:plain
(4,j)
{4 \times 4}の大きさの正方形が\(j \div 4\)個
\(+\) \(4 \times (j \% 4)\)の大きさの長方形（＝正方形の個数は既に\((j \%4,4)\)に代入されているのでこれを参照する）

以上を利用して実装したのが下記(Ruby)


Sponsored Link