「 今週のお題:一筆書きでクルクル」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 縦横4本・5本の道で構成された格子状の領域で、左上隅から右下隅まで、入力で指定された回数折れ曲がる行き方 ( 下の図は2回の例 ) が何通りあるか出力する。ただし、1度通った道は通らない ( 格子点は可 ) ものとする。
詳細は、CodeIQ magazineの当該記事をご覧ください。
解説
提出したのは次のRubyのコードでした。
f=->c,r,n{ g=->c,r,x,y,mx,my,n,d{ ((n>1?0:c)..c).reduce(0){|s,z| z==x||(n>e=d-w=(z-x).abs)||(0<mx&mp=((1<<w)-1)<<(y*c+[z,x].min))?s:s+(n<1?1:g[r,c,y,z,my,mx|mp,n-1,e]) } } d=r*c*2+1 n<1?0:g[c,r,0,0,0,0,n,d]+g[r,c,0,0,0,0,n,d] } p f[4,3,gets.to_i]
ちょっと詰め込んでるので分かりにくいかもしれません。冗長に書くと次のようになります。
f=->c,r,n{ g=->c,r,x,y,mx,my,n,d{ crange=n>1?(0:c):(c:c) #n=0,1の場合はゴールと同じ座標限定 crange.reduce(0){|s,z| next s if z==x #同じ地点へは行かない w=(z-x).abs #距離の増分 e=d-w #距離の余裕 next s if n>e #距離の上限に引っかかる地点へは行かない mp=((1<<w)-1)<<(y*c+[z,x].min) #新たに通る道のマスク next s if mx&mp>0 #重複する道は通らない n<1 ? s+1 : s+g[r,c,y,z,my,mx|mp,n-1,e] #n=0なら1通り追加、さもなくば再帰 } } d=r*c*2+1 n<1?0:g[c,r,0,0,0,0,n,d]+g[r,c,0,0,0,0,n,d] } p f[4,3,gets.to_i]
素直にDPで解くことができました。すなわち、再帰の形で書いています。
ソルバーのコアは関数 g ですが、これは、格子サイズ (c,r)、現在地 (x,y)、今まで通ってきた道のビットマスク (mx,my)、残りの曲がる回数 ( n ) を引数としています。
加えて、収束を早くするため、残りの距離の上限 ( d ) も設けます。
※全ての道 $(r+1)\times c+r\times(c+1)$本から、必ず通らない箇所ができる、スタート・ゴールの角、辺の三叉路、$2(r+c-1)$箇所で道の重複を考え $(r+c-1)$本を引いた $2rc+1$が初期の上限になります
移動は必ず横 ( サイズ c、位置 x ) で考えるものとし、縦の座標 ( y ) はそのままに、
現在地以外の場所に行った時の場合の数を足していきます。
なお、n=0,1の場合は、ゴールと同じ位置に合わせる必要がありますから、必ず端に移動します。
方向を横と限定する代わりに、再帰的に g を呼ぶ毎に縦横のパラメータを交互に入れ替えます。本体の関数 f では、どちらの方向を先にするかで g を2回分呼び出します。
終わりに
n=20のケースでは、確か0.2秒ほどかかったと思いますが、非常にすっきりした形で書けたのには自分自身驚きました。再帰ははまると強力ですね。