「今週のお題：長方形から作る正方形」問題解答 ( CodeIQ )

CodeIQ

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 次のような規則で、辺の長さが整数である長方形を正方形に分割することを考える。
    • 長方形の短辺を一辺とする正方形を端から切り取る
    • 残りの形が正方形になるまで、( その時々の ) 短辺を一辺とする正方形を切り取る
  • 最終的に n 個の正方形に分割できるような長方形の中で、長辺の長さが m 以下のものの個数を数え出力する。( 縦と横の長さを入れ替えただけの形は同じものとみなす )
  • m,nはカンマ区切り1行で入力される。

解説

方針

まずは、元の長方形の形からどのように正方形が切り出されるのか考えてみます。ちょっと大きいですが、50×18の例です。

f:id:ange1:20160224032903p:plain

大きい順に、

  • 18×18の正方形2個
  • 14×14の正方形1個
  • 4×4の正方形3個
  • 2×2の正方形2個

計8個に分割されていることが分かります。

それでは、それぞれの正方形の個数はなぜこうなったのでしょうか…? ちょっと考えてみると、割り算の結果になっていることが分かります。

$$ \begin{eqnarray} 50&\div& 18&=&2\ldots 14 \\ 18&\div& 14&=&1\ldots 4 \\ 14&\div& 4 &=&3\ldots 2 \\ 4 &\div& 2 &=&2\ldots 0 \\ \end{eqnarray} $$

各割り算の商が正方形の個数に対応し、余りは次の割り算の除数 ( 正方形のサイズ ) になっていることが分かります。そして割り切れたところで終了。

…実はコレ、ユークリッドの互除法の計算そのものです。そして最後の除数 ( この例では 2 ) というのは、元の長方形の長辺・短辺のGCD ( 最大公約数 ) に他なりません。

ということは、逆に言えば、GCD g と、各正方形の ( 小さい順の ) 個数$q_k\,\,( k=1,2,3,\cdots )$ が分かれば、ユークリッドの互除法を逆回しすることで、元の長方形のサイズが分かるはずで、かつ、数列$q_k$の構成と長方形の形は1対1に対応するはずです。

この例であれば、

$$ \begin{eqnarray} 1\times 2&+&0&=&2 \\ 2\times 3&+&1&=&7 \\ 7\times 1&+&2&=&9 \\ 9\times 2&+&7&=&25 \\ \end{eqnarray} \\ 9\times 2=18,\, 25\times 2=50 $$

g をかけるのを最後にしているため値が半分になっていますが、途中途中の計算結果は正方形を小さい順に戻していった時の長方形の辺の長さに対応しています。

この計算を一般化すると、

  • $x_0=0,\ x_1=1$
  • $x_{k+1}=x_k\times q_k+x_{k -1}\,\,( k=1,2,3\ldots )$
  • 長方形の長辺・短辺 $gx_{s+1},\,gx_{s}$ ( $s$は$q_{k}$の項数 )

ということになります。では、正方形の個数 n, 長方形の長辺の長さの上限 m を考慮するとどうなるか。それは、

  • $\sum_{k=1}^s q_{k}=n,\,\,\,q_1\ge 2$
  • $gx_{s+1}\le m $

ということになります。なお、$q_1$は一番小さい正方形の数ですが、これは必ず2以上です。

これで状況が整理できました。正方形の個数 n から、合計が n になるような数列$q_k$を構成し、そこから計算した$x_{s+1}$に対して、$g$の値は$1\le g\le \lfloor\frac{m}{x_{s+1}}\rfloor$の範囲で任意に定めることができますから、結局長方形が$\lfloor\frac{m}{x_{s+1}}\rfloor$通りあることになります。
これを数列$q_k$毎に計算して合計すれば、求める答えになります。

実装

さて上では

なお、$q_1$は一番小さい正方形の数ですが、これは必ず2以上です。

と書いたばかりなのですが、計算上は$q_1=1$に固定して2項目以降を変化させても同じことで、実際そちらの方が分かり易いです。

そうすると、数列$q_k,\,x_k$の構成は、

  • $\sum_{k=2}^s q_{k}=n-1$
  • $x_1=1,\,x_2=1$
  • $x_{k+1}=x_k\times q_k+x_{k -1}\,\,( k=2,3\ldots )$

に変わります。

ということで実装し提出したのは、次のRuby(93)でした。

eval"M,N="+gets
p (f=->n,a,b{b<=M&&n>0?(1..n).reduce(0){|s,q|s+f[n-q,b,a+b*q]}:M/b})[N-1,1,1]

数列$q_k$を途中まで構成し、残りの状況に応じた長方形の個数の総和をreduceで計算するような再帰関数fを実装しています。
引数の変数a,bが数列$x_k$の隣接2項に相当します。最初にfを呼び出す時、$x_1,x_2$に相当する1,1を渡すようにしています。

なお、b ( $x_k$ の最新の値 ) が途中でm ( 長方形の長辺の上限 ) を超えた場合は、その先では明らかに 0通りになるため、途中で計算を打ち切るようにしました。
…そうしない場合、m=25 のケースに対応できないためで、実際1度TLEを食らいました。

おわりに

ユークリッドの互除法は、その拡張版がmodinv ( 合同式による方程式 $ax\equiv b$ の解 $x\equiv a^{-1}b$ ) にも使われる重要なアルゴリズムです。それを組み込んだ面白い問題ですね。