はじめに

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

問題

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

格子状の長方形の領域を、1つの隅から対角の隅まで最短距離で移動する
その距離は入力により与えられる
2点を結ぶ重複しない経路 ( 部分的に重なっても良い ) を全て使用して往復した時に、元の地点に戻る領域の形状の中で、最小の横幅を出力する
そのような形状がない場合は 0 を出力する

解説

以下、提出版のコードRuby(29)と説明です。

n=eval *$<
p n<(k=-~n&~n)?0:k

経路の数は ${}_nC_k$ なので、結局これが偶数となるような最小の k を求めることに他なりません。

ここで例えば、$n=71$ の場合、${}_nC_k$ を順に見ていくと

$$ \begin{eqnarray} {}_{71} C_{1}&=&\frac{71}{1} \\ {}_{71} C_{2}&=&\frac{71\times 70}{1\times 2} \\ {}_{71} C_{3}&=&\frac{71\times 70\times 69}{1\times 2\times 3} \\ \cdots \\ {}_{71} C_{8}&=&\frac{71\times 70\times 69\times 68\times 67\times 66\times 65\times 64}{1\times 2\times 3\times 4\times 5\times 6\times 7\times 8} \end{eqnarray} $$

と、約分しても素因数2が初めて残るようになるのは、$k=8$の時です。

これは詳細は割愛しますが、$71+1=9\times 8$ と、$71+1$ が $2^3$ の倍数であって$2^4$の倍数でないからです。なお、$n=2^r -1$ の形の場合は先に 0 が出てきてしまう、つまり ${}_nC_k$ が全て奇数になるため解なし ( 0を出力 ) です。

ここで一般に、m に対して m&-m によって m の $2^r$ 成分を取り出すことができ、m=n+1=-~n であれば -~n&~n です。
$n=2^r-1$ の形かどうかは、これと n の大小によって判別できます。

終わりに

同時期に出ていた「レッド・アンド・ホワイト問題」( 「レッド・アンド・ホワイト」問題解答 ( CodeIQ ) - ange1のブログ ) と同様、「シェルピンスキーのギャスケット」が絡んでくる問題でした ( こちらの方が先 )。

おかげで、一方で楽できたのは内緒です。