CodeIQ：移動量が最小のハンカチ落とし

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「移動量が最小のハンカチ落とし」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
n人に加えて鬼一人がハンカチ落としをしています。
ハンカチ落としでは、鬼以外の人が円になって座ったあと、鬼が円の外を走ります。
鬼が誰かの後ろでハンカチを落とすと、落とされた人は鬼が一周してくるまでの間に気付き、鬼を追いかけます。

なお、走る速さは全員が同じため、鬼が追い付かれることはないものとします。
また、落とされた人はすぐに気付いて追いかけ、落とした人はその場所まで一周回ってきて座るものとします。

このとき、鬼になった人は他の鬼と違う量だけ移動してハンカチを落とすことにします。
これを繰り返し、すべての位置に一度ずつハンカチを落とすことを考えます。
（すべての位置にハンカチが落ちた時点で終了します。）

最初に鬼はAの位置にハンカチを落とします。
例えば、4人の場合、1人分→2人分→3人分を順に移動して落とすと、すべての位置に一度ずつハンカチが落ちます。
同様に、3人の場合は1人分→4人分を順に移動、もしくは2人分→5人分を順に移動して落とす方法などが考えられます。

fig.1

このとき、鬼の移動量が最小になるような移動方法を求め、その移動量の和を求めてください。
上記の通り、3人の場合は5(1+4)、4人のときは6(1+2+3)が最小となります。
標準入力から整数 n が与えられたとき、鬼の移動量が最小となる移動方法の移動量の和を標準出力に出力してください。
なお、n は9以下の正の整数が与えられるものとします。

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

標準出力
6

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Min = 0xffffffff

def getMv(n, ptn, i)
	ret = i

	while ptn.include?(ret)
		ret += n
	end

	return ret
end

def solve(n, r, ptn, now)
#	printf("n=%d, r=%d, ptn=%s, now=%d\n", n, r, ptn.to_s, now)
	if r == 0 then
		s = ptn.reduce(:+)
		$Min = s if s < $Min
		return
	end

	for i in 1...n
		pos = now + i
		pos -= n if pos >= n

		next if ptn[pos] != nil

		mv = getMv(n, ptn, i)
		np = ptn.dup
		np[pos] = mv

		solve(n, r-1, np, pos)
	end
end

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

	n = line.to_i
	ptn = Array.new(n)
	ptn[0] = 0
	solve(n, n-1, ptn, 0)
	p $Min
end

解説

★★★なので結構難しいです。
というより、ルールを理解するのに時間がかかりました。

考え方

時間的には総当たりで行けます。
なので総当たりでパターンを作って最小を求めます。

パターンの作り方ですが次の様にします。
まずA〜の位置をA=0,B=1,…と要素番号として、その場所にハンカチを落とすための移動量を値とする配列を用意します。初期値がAが最初の鬼でその他はまだ鬼になっていないのでnilとして次の様になります。
[0, nil, nil]（3人の場合）

まずAの移動を解決します。n未満の任意の歩数移動します。ここではとりあえず2移動してみます。
配列の要素番号2はnilなのでまだハンカチを落とされたことが無いのでOKです。配列に移動量を記録して次の様になります。
[0, nil, 2]

今度はCの移動ですが、1移動した場合、（先頭に戻って）Aの場所ですがすでに数字があるのでダメです。次に2を試しますが2はすでに使われています。
そこで、2+n(n=3)を試します。5はまだ使われていないのでこれを使用します。配列は次の様になります。
[0,5,2]

これで全ての場所にハンカチを落としたので終わりで、この場合の移動量は7です。

この方法を全パターンチェックできる様に再帰などで実装すればOKです。

main

＄Minは最小の移動量を保持する変数で初期値は非常に大きい値にしておきます。
入力値を取得して数値にし、最初のパターンptn=[0, nil, nil, ...]を作ります。
silve()の引数は入力値、残りの場所の数、現在のパターン、現在位置なのでsolve(n, n-1, ptn, 0)を指定して呼び出します。

solve(n, r, ptn, now)

考え方の通りに全パターンを試し、最小の移動量を求めます。
引数nは入力値です。
引数rは残りの場所の数です。
引数ptnは場所ごとにハンカチを落とされた時の移動量を記録した配列です。
引数nowは現在の場所です。

まずrが0の場合は全箇所を回った状態なのでptnの合計を計算し、合計が$Minより小さかったら$Minを更新して戻ります。

rが0以外なら1〜(n-1)の移動を全て試します。
現在位置はnow+iになる（末尾を超えたら先頭に戻す）ので移動後の位置をposとします。
もし、ptn[pos]がnilで無いならその場所はすでに回っているので無視します。
そうでなければ、getMv()を使って何歩でその場所に行けるかを求めます。
ptnのコピーを更新し、rを1減らし、posを現在位置として再帰的にsolve()を呼び出します。

再帰呼び出しが最初まで戻ったら全パターンチェックが終了し$Minが答えになっています。

getMv(n)

i歩に最も近い、ptnですでに使われていない、最小の移動量を計算します。
引数nは入力値（=1周回るための歩数）です。
引数iは候補の歩数です。
ptnはすでに使われた歩数です。

retは最小の歩数で初期値はiと同じです。
retがptnにあればretをn増やした値をテストします。これはretがptnになくなるまで繰り返します。retがptnになければその値を返します。
これで必要な歩数を求めることができます。

雑感

配列のコピーはしているし、値の重複チェックも手間がかかっているので結構遅いロジックですが、nの最大は9で、実際のところ8回の移動が最大なので総当たりでなんとかなりました。