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通りあり、これが最大です。

fig.1

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

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

標準出力
4

私のプログラム

Rubyで解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/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の時にはとんでもない大きさの数になることは容易に想像できます。なので、パターンを作ってカウントしていたのでは絶対に間に合いません。
しかし、入れ子になっているマトリョーシカ人形のことは考えず、見えている人形だけなら2n-1程度のパターン数しかありません。なので、n=1の時のパターン数（1）は明らかなのでこれを元にn=2を計算し、n=2の結果からn=3、とパターン数だけを数えればできそうです。
が、この方法がわかりません。

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/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は21、4は22、9は32、27は33、81は34、256は44でしょう。ということは2つ目の1は11で、1つ目は10か00に思えます。

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

solve()

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

雑感

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