CodeIQ 挑戦の記録 : 今週のアルゴリズム : 第94回「一筆書きでクルクル」

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

f:id:ibeckuu:20160523223811j:plain

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

横に4本、縦に5本の道路が並んだ格子状の地図がある。
左上の地点から右下の地点まで移動する。一度通った道は通れないものとする。
標準入力から直角に曲がる回数が指定され、ちょうどこの回数を曲がって左上から右下へ到達する経路が何通りあるかを解答する。

方針

再帰関数で探索して求める。
引数は以下の4つ

曲がった回数
現在の位置
横方向の点の個数と縦方向の点の個数の積で整数値にエンコード
一つ前にいた位置
現在位置と同じく整数値
それぞれの道について既に通ったか、通っていないかの状態
2点間の道に番号をつける。(横方向は2点の内小さい方の番号、縦方向は小さい方の番号+縦横の個数の積。0から35までの数値) この番号をフラグとしてビット演算で整数値にエンコード

再帰関数にて左上から右下までの一筆書きでの移動を試し、曲がった回数が所定のn回に一致するものを数え、解答とする。

考察

というか反省。
うまくメモ化できなかったのでメモ化なしの再帰で提出した。
結果は全てのケースで0.08秒でACだったためクリアできてよかったが、最適な解には程遠いと思われ、納得が行かない。

データ構造について、

今回、都合により全く時間がとれず、データ構造についていろいろ試してみる事が出来なかった。
取った方法はデータを全て整数値にエンコードし、4次元配列を用いてメモ化するコードを書いたが、4つの内1つの要素数が ${{2}^{36}}$ という巨大なものになった為、メモ化であるのに、実行すると全く答えが返ってこない状態になり、早々にメモ化を諦めた。
ビット演算で状態を持つのではなく、単純にハッシュにすれば良さそうにも思ったが、3次元配列の中にハッシュが入れ子になっている構造を実装する気になれず、また、仮引数にハッシュを渡していわゆるシャローコピー（浅いコピー）で意図しない動きになる事を回避する（Marshalを使う）のも面倒だったので試してない。

実装 (Ruby)

では、