はじめに

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

問題

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

縦横4本・5本の道で構成された格子状の領域で、左上隅から右下隅まで、入力で指定された回数折れ曲がる行き方 ( 下の図は2回の例 ) が何通りあるか出力する。ただし、1度通った道は通らない ( 格子点は可 ) ものとする。

解説

提出したのは次の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秒ほどかかったと思いますが、非常にすっきりした形で書けたのには自分自身驚きました。再帰ははまると強力ですね。

ange1のブログ

「今週のお題：一筆書きでクルクル」問題解答 ( CodeIQ )

はじめに

問題

解説

終わりに