「 今週のお題：永遠に続くビリヤード」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- カンマ区切りで与えられる整数m,nに対し、m×nの格子を考える。
- 格子点から斜め45°にビリヤードの要領でボールを打ち、壁・隅で反射しながら十分に長い距離をボールが進む時、ボールが通るマスの数の最小値・最大値を1行ずつ出力する。
例えば、m=4,n=6 ( 入力: 4,6 ) の場合であれば、次の図のようなボールの進み方があるため、最小が12、最大が24となります。
解説
提出コードは次のRuby(39)でした。
eval"M,N="+gets p a=M.lcm(N),a*=2-a/M/N
m,nが互いに素の場合は、どこを起点にしても全マス通るので、最小値・最大値ともに m×n です。
問題は互いに素でない場合。
- 最小は、隅から出発して別の隅に到着するパターンで、lcm(m,n)マスです。
- 最大は、隅でない場所から出発して、途中隅に立ち寄ることなく、出発地点に戻ってくるパターン。これは最小値の2倍です。
最小のケースは、互いに素でもそうでない場合も含めて lcm(m,n) でまとめることができ、最大のケースに関して2倍するかどうか、互いに素かどうかは、このlcm(m,n)とm×nの大小で見ることができるため、2-a/m/n ( 除算は端数切捨て ) という1つの式にまとめることができます。
…なんでそんな簡単な式になるの? ということで、補足しますと。
まず、同じマスを次の図のように、違う方向から重複して通ることはありません ( 偶奇性を考えるとそうなります ) ので、通るマスの数は、純粋に「反射によって同じ格子点に帰ってくる」までの移動距離で測ることができます。
で、最小のケース。これはどこかの隅から出発して隅に到着するケースです。隅での反射は、完全に往路を逆に辿りますから、「同じ格子点に帰ってくる」を考えるまでもなく、隅～隅の移動距離で済みます。これが lcm(m,n) です。
では最大のケースは、というと。m,n が互いに素の場合、既に lcm(m,n)=m×n ですから全マス通っており、最小値と一致します。これは「互いに素であれば、必ず隅に到着する」ことを表します。しかし互いに素でない場合は、隅を通らない経路が存在します。そのような経路では、左右の往復と上下の往復の同期がとれたところで元の格子点に戻ってきますから、lcm(2m,2n) ということで最小値の2倍になるのです。
終わりに
気付くと数式自体は簡単なので、実装は驚くほど短く済む問題でした。lcm や、使っていませんが gcd が一発で出せるRubyも便利ですね。
