CodeIQ 「ロンリー・ルーク」問題の解答コード公開
久々の投稿になります。
今回はCodeIQの問題の解答コードを公開します。
問題
今回の問題の概要です。
方針
F(n, k)について、k=1~mまでの和を求めるので、F(n,k)の値の求め方を考えます。
- k=1の場合、「はぐれルーク」は1個なので期待値は1
- k > n-1の2乗+1の場合、どう配置しても「はぐれルーク」は無いので期待値は0
- kの値が上記以外の場合について、全配置の組み合わせについて「はぐれルーク」の個数を計算
まあ、要はしらみつぶしというやつですww
解答
以下が、提出したコード。n×n の盤面を1次元配列で表現しているのが多少の工夫といえば工夫かも。
def func(n, k) return 1.0 if k == 1 return 0.0 if ((n - 1) ** 2 ) + 1 < k numOfLonelyLuke = 0 numOfCombination = 0 (0..(n**2 - 1)).to_a.combination(k) do |array| numOfCombination += 1 array.each do |x| isLonely = true array.each do |y| next if x == y if (x / n == y / n) || (x % n == y % n) isLonely = false break; end end numOfLonelyLuke += 1 if isLonely end end numOfLonelyLuke / numOfCombination.to_f end (n, m) = gets.split.map(&:to_i) num = 0.0 (1..m).each do |k| num += func(n, k) end puts (num *1000).to_i
感想
今までもCodeIQの問題は解いてましたが、公開するのは今回が初めてです。
また、この機会に他の方の解答コードを見てみましたが、エレガントな解法で実装されてる方が結構いらっしゃったので驚きでした。
次はもう少し綺麗な解き方を目指すようにしないとなー。
ま、自分もまだまだ精進が必要だなーと感じ入りました。ほんと。(´Д`)