CodeIQ：同じ数字でサンドイッチ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「同じ数字でサンドイッチ」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

1～Nまでの数字が掛かれたカードがそれぞれ2枚ずつと、ジョーカー1枚があります。
このカードを一列に並べるとき、書かれている数字の数だけ他のカードを挟んで並べることにします。
（ジョーカーは挟まれるだけで、挟む必要はありません。）

例えば、1, 2, 3のカードがそれぞれ2枚あるとき、ジョーカーを「0」で表すと
2, 3, 1, 2, 1, 3, 0
2, 3, 0, 2, 1, 3, 1
…
などのように並べられます。
※いずれも1で挟まれたカードは1枚、2で挟まれたカードは2枚、3で挟まれたカードは3枚です。

N=5のときは、以下のような例で挟めます。
1, 5, 1, 2, 3, 4, 2, 5, 3, 0, 4
1, 4, 1, 5, 3, 0, 4, 2, 3, 5, 2
…

標準入力から N が与えられるとき、上記のように挟んだ並べ方の中から、ジョーカーが最も右側に来る並べ方を求め、その位置を標準出力に出力してください。
例えば、N=3, N=5 のときは上図のそれぞれ一行目が該当しますので、以下のように出力します。

Nは9以下の正の整数とし、上記のような挟み方が存在しない場合は0を出力してください。

【入出力サンプル】
標準入力

3

標準出力

7

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$POS = 0

def getPos(pos)
	i = 0
	while (pos & (1<<i)) != 0
		i += 1
	end
	return i+1
end

def solve(n, m, now)
#	printf("n=%d m=%d now=%s\n", n, m, now.to_s(2))
	if m == 0 then
		x = getPos(now)
		$POS = x if x > $POS
		return
	end

	pos = (1 << (m+1)) | 1
	for i in 0...(n*2-m)
		nxt = pos << i
		next if (now & nxt) != 0
		solve(n, m-1, now | nxt)
	end
end

# main
while line = gets
	line.strip!
	next if line.empty?

	solve(line.to_i, line.to_i, 0)
	p $POS
end

解説

★★★の問題です。
基本的な部分（書かれている数字の数だけ他のカードを挟んで並べる）は以前同じ様な問題をやっていたのですぐにわかりました。
以外に総当たりでも時間は足ります。

考え方

まず、ジョーカーは0と考えます。0なら間に挟まれる数字は無いのでちょうどうまい感じです。

数字を並べるのは次の様にします。
まず、全ての数字を並べた場合、2n+1枚のカードが並ぶことになりますので、その分の領域を用意します。
次に最も大きな数字から次の様に処理します。
配置する数字をmとし、1枚目を左側に配置すると、2枚のカードはm+1右側に配置されます。この位置関係は崩れません。なので1枚目を左からi番目に配置すると2枚目はi+m+1番目に配置されます。
数字mのカードを配置しようとしたとき、1枚目か2枚目のカードの場所にすでにカードが置かれていたらそのパターンは無視します。
これを最後まで繰り返せば配置のパターンを列挙できます。

あとはジョーカー(m=0)まで配置したときの0の位置のうち一番右側にあるものを求めればOKです。

main

$POSは最も右側にジューカーが置かれたときの位置の最大値を保持する変数です。
入力値を数値にしてsolve()に渡し、結果を得ます。

solve(n, m, now)

引数nは入力値です。
引数mは配置するカードの番号です。最初の呼び出し時はnと同値になります。
nowはカードがすでに置かれている場所を1、置かれていない場所を0とした整数です。配置が決定したカードの番号は関係ない（その場所にカードがあるかどうかだけが重要）なので処理の高速化のためこの様にしました。なお、問題とは左右反転して扱います。

15〜19行目はジューカーが置かれる場合（m=0の場合）で、getPos()でその場所を求めます。このときnowの中で最初に0になるビットをジョーカーの位置とする（他の場所は1で埋まっているので1の連続の中から0を探す）ため、ジョーカーの場所のビットを立てる処理はしません。
位置が求まり、$POSより大きかったら$POSを更新します。

21行目の処理で数字mのカードを配置する場所を決めます。
例えば、m=3ならpos=0b10001になるので問題の通りに配置できます。

22〜26行目のループで配置可能な場所を全て試します。
1枚目のカードが(n*2-m)番目になったら配置可能な領域からはみ出すのでその前までが配置可能な場所になります。
posをiビット左シフトしてnowと論理積をとった気に0でない場合、同じ場所にはすでにカードが置かれていることになります。なので無視します。
posとnowの論理積が0ならsolve(n, m-1, now | nxt)を再帰呼び出しします。

getPos(pos)

ジョーカーの位置を探します。
ジョーカーの位置は0b11011111の様になっている0の場所なのでビットシフトしながら位置を探します。
答えは0始まりでなく1始まりなので結果を+1して返します。

雑感

最初に書いた様に一度カードの間にその数字枚数のカードを配置する問題をやったことがあったので配置を作るのは簡単に考えつきました。
ただ、総当たりしか方法を思いつかず（うまくメモ化する方法を考えつかなかった）、とりあえず時間計測してみて考えようと思ったら、0.2秒あまりで終わったのでそのまま解答としました。