CodeIQ：一列に並べたマトリョーシカ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「一列に並べたマトリョーシカ」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

サイズが 1～n まですべて異なる n 個のマトリョーシカ人形があります。
このマトリョーシカ人形を一列に並べることにします。
なお、マトリョーシカ人形では、大きなサイズの人形の中に、小さなサイズの人形を入れられます。

例えば、n = 4 のときの並べ方を、最も外側にある人形のサイズで表すと、以下の8通りがあります。

4 ←　残りの人形がすべて中に入っている
4 3
4 2
4 1
4 3 2
4 3 1
4 2 1
4 3 2 1 ←　すべての人形がバラバラになっている

それぞれについて、内側にある人形の配置パターンが何通りあるかを考えます。
例えば n = 4のときは、「4 3」のときに1と2の人形の配置が以下の4通りあり、これが最大です。

標準入力から n が与えられたとき、そのパターン数の最大値を標準出力に出力してください。
(n は最大で16とします。)

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

4

標準出力

4

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 総当たりの実験結果からOEIS A003320の数列になると予想
def solve(n)
	mx = 0
	for k in 0..n
		v = k ** (n-k)
		if mx < v then mx = v end
	end
	return mx
end

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

	n = line.to_i
	p solve(n)
end

解説

★★★の問題です。コードは非常に短いですが非常に難しいです。それ以前に私はなぜこのロジックで答えを求められるかがわかりません。

やったこと

私にはなぜこのコードで答えが求められるのかわからないと書いた通り、このコードで答えを求められるかを説明できません。なのでどうやってこのコードにたどり着いたのかを説明します。

テストケースの最悪のパターンn=16の時にはとんでもない大きさの数になることは容易に想像できます。なので、パターンを作ってカウントしていたのでは絶対に間に合いません。
しかし、入れ子になっているマトリョーシカ人形のことは考えず、見えている人形だけなら2^n-1程度のパターン数しかありません。なので、n=1の時のパターン数（1）は明らかなのでこれを元にn=2を計算し、n=2の結果からn=3、とパターン数だけを数えればできそうです。
が、この方法がわかりません。

仕方ないので時間が足りないのはわかっていますが実際に例のn=4にあるような、外から見えるマトリョシカ人形のパターンに対してそれぞれ入れ子にできるパターンがどれだけあるかを実際に作ってみるコードを書きました。

#!/usr/bin/ruby

$Patterns = []
$Filled = {}

def makePattern(n, arr)
	if n == 0 then
		$Patterns << arr
		return
	else
		nxt = arr + [n]
	end

	for i in 0...n
		makePattern(i, nxt)
	end
end

def toArrayList(ptn)
	ret = []
	for v in ptn
		ret << [v]
	end
	return ret
end

def copyArrs(arrs)
	ret = []
	for a in arrs
		ret << a.dup
	end
	return ret
end

def fill(arrs, rest, key)
	if rest.empty? then
		if $Filled[key] == nil then $Filled[key] = [] end
		$Filled[key] << arrs
		return
	end

	r = rest.dup
	v = r.shift

	for i in 0...arrs.size
		nxt = copyArrs(arrs)
		if nxt[i].last > v
			nxt[i] << v
			fill(nxt, r, key)
		else
			break
		end
	end
end

def solve(n)
	makePattern(n, [])

#	p $Patterns

	for ptn in $Patterns
		rest = (1..n).to_a.reverse - ptn
		arrs = toArrayList(ptn)

#		printf("%s, %s\n", arrs.to_s, rest.to_s)
		fill(arrs, rest, ptn)
	end
end

def printResults(results)
	results.each{|key, val|
		printf("%s : %s\n", key.to_s, val.to_s)
	}
end

def printCounts(results)
	max = 0
	results.each{|key, val|
		printf("%s : %d\n", key.to_s, val.size)
		if max < val.size then max = val.size end
	}
	return max
end

# main
n = ARGV[0].to_i
solve(n)
printResults($Filled)
max = printCounts($Filled)
printf("max=%d\n", max)

詳しい説明はしませんが、簡単に言うと次のようなことをしています。
まず、表に見えているマトリョーシカ人形のパターンを列挙します。
それぞれのパターンに対してどのように入れ子にできるかを全パターン作ります。

これを実行すると（問題とは異なりコマンドライン引数にパラメータをとります）、実際の入れ子のパターン、表に見えているマトリョシカ人形ごとの入れ子のパターン数、最大になる入れ子のパターン数を印字します。
これでn=10か11くらいまでは出力を待てる程度の時間で結果を表示できます。

で、最大値のみの結果を並べてみると1, 1, 2, 4, 9, 27, 81, 256と言う数列になりました。
これは特徴があります。
2は2¹、4は2²、9は3²、27は3³、81は3⁴、256は4⁴でしょう。ということは2つ目の1は1¹で、1つ目は1⁰か0⁰に思えます。

こういう時に役立つのがOEISで、検索したら見事にヒット！
それがA003320です。
どういう数列かは簡単でk^(n-k)の最大値（ただし、kは0〜n）です。
実際に試してみたら前述の総当たりの結果とn=11まで一致します。
何でこうなるのかがわからないので確信は持てませんが、11個も数列が一致するならあっているだろう（違っていたらギブアップするしかない）ということで解答のコードとなりました。

solve()

もう説明してしまいましたが、k^(n-k)の最大値（ただし、kは0〜n）を返します。
これが答えになります。

雑感

何でこうなるのかなぁ？誰か教えてください。