読者です 読者をやめる 読者になる 読者になる

「 今週のお題:まわり将棋に挑戦!」問題解答 ( CodeIQ )

CodeIQ

はじめに

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

codeiq.jp

問題

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

  • 入力 n に対し、まわり将棋 ( 参考: Wikipedia ) で、隅から出発して、n 回後の手番で再び隅にいるための目の出方は何通りあるか出力する
  • 移動する距離は、金将の駒4枚のそれぞれの出方に対応した数字の合計で決まる。
    • 表が出れば 1
    • 裏が出れば 0 ( ただし、4枚全部裏の場合は合計8と見做す )
    • 横に立てば 5
    • 縦に立てば 10
    • 縦で上下逆に立てば 20
    • ただし、駒同士が重なる等の無効な目は合計 0 と見做す
  • 駒の出方が異なる場合でも、移動するマスが同じであれば区別しない

例えば n=1 の場合は、0マス, 8マス, 16マス, 32マス, 40マス, 80マスの6通りが答えとなります。

解説

提出したのは次のRubyのコードです。

p gets.to_i.times.reduce([1]+[0]*7){|v|s=v.reduce(&:+)*5;v.map{|e|e+s}}[0]

目の出方は、無効な目である 0 を除くと、${}_5H_4=70$通りありますが、進む数が等しい場合は区別しないことから、実際には 40通りとなります ( 詳細は割愛します )。

そして、移動に関してはあくまで「隅に来るかどうか」ですから、$mod\,\,8$で考えれば良く、$mod\,\,8$で分類すると、0~7 まで全て 5通りずつとなります。無効な目を入れると 0 のケースだけ6通りです。

そのため、n回振った後に隅から何マスの所に来ているか、場合の数はベクトル列として、次のように計算することができます。

$$ \bf x_{0}= \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\ $$ $$ \bf x_{n}= \begin{pmatrix} 6 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 5 & 6 & 5 & 5 & 5 & 5 & 5 & 5 \\ 5 & 5 & 6 & 5 & 5 & 5 & 5 & 5 \\ 5 & 5 & 5 & 6 & 5 & 5 & 5 & 5 \\ 5 & 5 & 5 & 5 & 6 & 5 & 5 & 5 \\ 5 & 5 & 5 & 5 & 5 & 6 & 5 & 5 \\ 5 & 5 & 5 & 5 & 5 & 5 & 6 & 5 \\ 5 & 5 & 5 & 5 & 5 & 5 & 5 & 6 \end{pmatrix} \bf x_{n-1} $$

なお、隅から$i$の位置に来る場合の数は、ベクトル$\bf x_n$の$i$行目の要素に対応します。なので、隅の場合は先頭の要素です。

実装については、初期ベクトル$\bf x_0$ に次々係数行列をかけていくのに相当した処理をループで行っています。行列のべきをバイナリ法で行えば$O(log n)$で速いのですが、今回計算量には頑張っていない解法です。

終わりに

数列と行列というのは、やはり切っても切れないところですね。すっきりと関係を表すことができます。…記事で数式を書くのは大変なのですが。