「今週のお題:左右に行ったり来たり」問題解答 ( CodeIQ )

はじめに

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

codeiq.jp

問題

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

  • 標準入力から入力される自然数n ( $n \le 12$ ) に対して、次のような条件を満たす横1列nマスの配置の組み合わせが何通りあるか出力する
  • 右端の0を除き、各マスには1~n-1の数字を入れる
  • 左端を起点として、右・左と交互に、マスに入っている数字分だけ移動することで、配置されているマスからはみ出すことなく、全てのマスを1度ずつ通ることができる

以下は、問題文にあった n=6 の場合の例です。右側にある4通りが条件を満たしているもので、うち1例について、左側の図で実際に1度ずつ通れることを示しています。

https://codeiq.jp/sites/default/files/answer_ready/3210/q75.png

解説

まず問題文を変形します。
実はマスに書いてある数字がなんであるかを気にしなくても、結局問題なのは「どのような順番でマスを辿るか」です。その上で「右・左交互に動く」ということは、始点と終点を除いて、「途中 n-2 個のマスに相当する 1~n-2 の順列の中で、増・減を交互に繰り返すもの」を挙げるのと同じことです。
※なお、この時点で n が奇数の場合条件を満たす組み合わせなし、答え 0 と分かります

問題文にあった例からこの順列を作り出すと、次の図のように2,1,4,3となります。

f:id:ange1:20170326160730p:plain

なので、最悪でも、このように増減を繰り返す順列を作り出していって個数を数えれば正解を導き出すことができます。

が、もうちょっと考えてみます。

ある所まで順列を構成したところで、その後どれだけの順列が作れるかを見てみます。n=10で4つ数字を決めた2つの状況ですが、この後数字そのものが違うにしても、本質的に同じ並べ方になっています。

f:id:ange1:20170326171855p:plain

これは、後の並べ方に効いてくるのが、最後に選んだ数字の前後に幾つ未使用の数字が残っているか、だけであるからです。( 上の図中の紫/青のマスの数 )
そのため、このマスの数のペアをキーとしてメモ化再帰をかけることが考えられます。なお、向きを揃えるため、2つずつ数字を選んで状況を進めていきます。

そうすると、先ほどの図の「前 1、後 3」の状況から例えば「前 1、後 1」へ移る時のことを考えると、最後に選ぶ数字は固定になりますから、その直前が何通りか、これが倍率として効いてくることになります。次の図のように ? のついているいずれかのマスを経由して、b のマスに戻って来ることになりますから 2 通りです。

f:id:ange1:20170326185858p:plain

実際に計算する場合には、残りを前・後に幾つずつ割り振るか、全ての状況に対して総和を取ることになるのですが、前に少なく残す場合と多く残す場合では、やや倍率が変わって来ることに注意が必要です。

ということで、提出版のRubyです。

p ->n{
  n.odd? ? 0 :
  (f,h=->pre,post{
    h[[pre,post]]||=(t=pre+post-1).times.reduce(0){|s,i|
      s+f[i,t-i-1]*(i<pre ? post : t-i )
    }
  },{[0,0]=>1})[0][0,n-2]
}[gets.to_i]

終わりに

今回かなり綺麗に再帰の形で書けました。n の上限は 12 でしたが、このコードの場合かなりメモの効果が効くのか、n をもっと大きくしても耐えらるようです。