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

CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第103回「まわり将棋に挑戦!」

CodeIQ

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

  • まわり将棋を考える
    (まわり将棋とは金将4つをサイコロの代わりに使い、9x9マスの将棋盤の周囲を双六の様にコマを進めるゲームである)
  • 振った金将の状態により金将1つあたり下記の得点が得られる。4つの合計が進むマスの数となる。
    ・裏向き:0
    ・表向き:1
    ・横向き:5
    ・上向き:10
    ・下向き:20
  • あるコマが角の位置からスタートした時、n回振って4つの角の内どこかの角にいるパターンが何通りかを解答する。
  • コマの動きは動くマスの数のみに着目する。並び順は区別する。
    例えば n=2 のとき、「1回目に3マス、2回目に5マス」動いたときと、「1回目に5マス、2回目に3マス」動いた場合は別々とカウントする。
  • nの最大は7

方針

メモ化再帰により探索する。
金将4つの得点の合計が1回に進むマスの数になり、これのn回の和が進んだマスの数。
9x9マスの周囲を回るので、角からスタートすれば、進んだ数が8の倍数であればどこかの角にいる事になる。

実装としては、あらかじめ金将4つの得点の合計の組み合わせ
{0,1,5,10,20}の中から4つを選んだ組み合わせの和を計算し、配列に記録しておく。
n回コマを振った場合に進む、全てのコマ数の組み合わせをメモ化再帰で試し、合計が8の倍数になるものを数え解答とする。

実装(Ruby)

では、


Sponsored Link