「ストレート・ラインズ」問題解答 ( CodeIQ )
CodeIQというところでプログラミング問題「ストレート・ラインズ」に解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 入力される自然数 $n\,(2\le n\le 40)$ に対し、$F(n)$を計算し、出力する
- $F(n)$ とは、格子状に並んだ$n$行$n$列の点の内、2点のみを通る直線の本数である
例えば、問題に挙げられていた次の画像のとおり、$n=2$ならば条件を満たす直線は6本、$n=3$ならば12本、つまり$F(2)=6,\,F(3)=12$ と分かります。
解説
直線が通る2点の、縦・横の距離に着目します。で、これらの距離が非ゼロかつ互いに素でないとマズいのはtrivialなので割愛。ただ、$n=2$の場合の$(1,0)$の組み合わせは例外です。
その上で、以下のように条件を絞ります。
- 2点の縦の距離より、横の距離の方が長い
※(1,1)が例外的に「縦と横が等しい」かつ「互いに素」なのですが、これは別途処理します - 直線が左上がり ( 右下がり )
ここは対称性が効いてくるところなので、カウントした後4倍すれば済むからです。なおもちろん、縦横逆で考えたり、左下がりで考えても構いません。
その上で何本線が引けるかを考えていくわけですが、この「距離」( 特に長い方の横 ) によって状況が変わります。なぜなら、「互いに素」という条件によって、選んだ2点の中間の点を通る可能性は排除されているものの、その外側がどうか、という条件が変わってくるからです。
- 横の距離が十分大きい場合
これは外側に通る点ができることを考える必要がありません。なので、格子内目一杯直線を引けば良いです。例えば次の図のように、8×8格子で横4縦3の距離の2点を通る直線であれば、$(8-4)\times(8-3)$で本数が計算できます。
- 横の距離が十分小さい場合
これは、直線を少し中央に寄せるだけで、容易に外側の点を通るようになってしまいます。なので、端に寄った位置にしか直線を引けません。例えば次の図のように、10×10格子で横3縦2の距離の2点を通る直線であれば、そのまま$3\times 2$の本数が、右上・左下の端の2か所分で計12本引けると分かります。
- それ以外 ( 横の距離が中途半端な場合 )
このケースが最も複雑です。直線を少し中央に寄せると外側に通る点ができてしまうのですが、中央付近だと逆に大丈夫という状況です。これは、上2ケースが混じり合った状態と見ることもできます。例えば次の図のように、10×10格子で横4縦3の距離の2点を通る直線であれば、上の2ケースに相当するような範囲が重なりあっている部分が該当すると分かります。
というわけで提出版のRuby実装です。$n=2$の場合だけは別として、後は上で挙げた3ケースの組み合わせ分本数を数え、最後に4倍するというシンプルなものです。なお、4倍する前の本数aにセットしている初期値1は、横1縦1の分を予め数えているものです。
終わりに
シンプルな実装ではあるものの、計算量は$O(n^2)$であんまり今回頑張れませんでした。本当は互いに素な組み合わせを全体から選ぶ代わりに、何かしら少数のベースを用意し、その倍数の距離になっているものを一括で扱えた方が速いと思ってはいたのですが…。 togetterにあるまとめに紹介されているコードは、そういった方法で高速化を実現化しているものがあるようです。凄いですね。
