日々の破片

_ 配列を作る

aからbまでを要素に持つ配列の作り方。

(a..b).to_a

（いつも忘れるのでメモ）

_ 再帰ではない方法

TopCoderの最初の練習問題（チュートリアルではなくアリーナのほうのやつ）のアドバンスがどうやってもできずにえらく悩む。

1から与えられた数までの集合（たとえば、与えられた数が4なら、1,2,3,4）から、与えられた桁数を埋める数字を作る（たとえば与えられた数が3なら、123とか431とか）。

この時、作られた数字の並びが、左側に対して等しいか大きくなるような数は何通りできるか？ という問題。たとえば、上の集合と桁であれば、123はOK、111もOK。でも、121はNG。

これは再帰を使えばすぐに解ける。といってもすぐにできたわけではないのが悲しいところであるが。

#最後のパラメータはデバッグ用
def count_r(start, range, depth, a)
  if depth == 0
    p a if $DEBUG
    return 1
  end
  r = 0
  start.upto(range) do |is|
    a.push is
    r += count_r(is, range, depth - 1, a)
    a.pop
  end
  r
end
puts "4, 3(r)=" + count_r(1, 4, 3, []).to_s
puts "4, 4(r)=" + count_r(1, 4, 4, []).to_s
puts "4, 5(r)=" + count_r(1, 4, 5, []).to_s
puts "93, 8(r)=" + count_r(1, 93, 8, []).to_s

最初の3つはすぐに求まる。

4, 3(r)=20
4, 4(r)=35
4, 5(r)=56

だが、4つ目（実際の問題のINDIGOのはず）は無限とも思われる時間がかかっても終わらない。もちろんYARVじゃなくてJavaで書いても同じだ。

ということは、もっと賢い（というか、全件を求めているのだから単に力任せで少しも賢くはないから、「もっと」というのは変だな）アルゴリズムがあるはずだ。

が、これがわからない。頭の中には左から右に枝分かれする絵があるのだが、再帰を使ってすべての枝をたどる方法ではなく、それを計算で求める方法がわからない。

で、考えていた。ほぼ1日。正味でも数時間かも。

さっきわかった。1から4の場合であれば

[1, 1, 1, 1]
[4, 3, 2, 1]
[10, 6, 3, 1]
[20, 10, 4, 1]

ということか（数字自体は見えていたのだが、配列に入れることで求め方がわかったということ）。その要素から右端までの要素の総和が次ぎの要素となる。

それにしても、こういうの(あるいはもっと賢い方法)をさっと考えつく人がうじゃうじゃいるわけだから、世の中は広い。