「 今週のお題:一筆書きの交点」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

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

  • 入力 n に対して、周上に等間隔に並んだ n 個の点を直線で結んで一筆書きする時、結んだ直線同士の交点の数を全ての一筆書きのやり方について合計した数を出力する。

この「交点」って何ぞや? というと、n=5 の例としては、次の図 ( 図中の赤× ) のようなものがあげられます。一筆書きは向きありで考えるため、同じ経路でも逆順は別として扱います。

f:id:ange1:20160418212646p:plain

なお、n には 9 という上限が設けられていました。下限は特に書いていませんが、一応ケース的には3以上でした。

解説

まず、一筆書きってどれだけやり方があるんだろう…というところから考えてみます。

先ほどのn=5の図で、各点に番号を振ってみました。一筆書きなのでどこから始めても同じなのですが、便宜上1から ( 1まで ) としてみます。そうすると、これは残り2~4の順列 2-4-5-3 と対応していることが分かります。

f:id:ange1:20160418212848p:plain

ということで、円順列と同じ考え方で、全部で$(n-1)!$通りあることが分かります。

さてそうすると、一筆書きの方法をまず全て挙げることはできるのですが…。ただ、そこから1つ1つ交点を調べていくとすると結構大変です。なので、ここで発想を転換します。先に交点を見るのです。

例えば、点1,a,b,c ( $1\lt a\lt b\lt c$ ) の4点が絡む交点は、この4点を頂点とする四角形の対角線の交点1つのみです。一筆書きの順序を考えると、それぞれ$n-3$通りが4セットで、a,b,cの決め方が$4(n-3)$通りあることになります ( 次図参照 )。

f:id:ange1:20160418220504p:plain

そして、それ以外の点の順序の決め方が$(n-4)!$通りありますから、結局この交点が現れる一筆書きは$4(n-3)\times(n-4)!$通りだと分かります。

これで1交点での状況が分かりましたが、1の絡まない分も含めて、他の交点での状況が全て同じということもすぐに分かります。交点は4点の選び方${}_nC_4$個分ありますから、結局、

$$ \begin{eqnarray} & &4(n-3)\times(n-4)!\times{}_nC_4 \\ &=&4(n-3)\times(n-4)!\times\frac{n!}{(n-4)!\times 4!} \\ &=&\frac{1}{6}(n-3)\times n! \\ \end{eqnarray} $$

が最終的に求める答えです。…n=3のときはそもそも交点0個なのですが、同じ数式で表現できています。

$\frac{1}{6}$の部分は、階乗の計算から1,2,3を除くことで対処できるので、次のRuby(33)で実装できます。
※あ。reduceの呼び出し、カッコ無くてもいけるので32文字でいけましたね。

p (4..n=gets.to_i).reduce(n-3,:*)

このような計算であれば、Brainf**kでもいけますね。nの上限が9なので、繰り上がりを1桁分だけケアした10進掛け算で実装できます。
※これで263文字です

終わりに

ここのところBrainf**kで組んでなかったのでちょうど良かったかな…という感じで。