或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

CodeIQ 「ロンリー・ルーク」問題の解答コード公開

久々の投稿になります。
今回はCodeIQの問題の解答コードを公開します。

codeiq.jp

問題

今回の問題の概要です。

  • 自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置します。このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。
  • 1 つのマスに 2 個以上の駒を置かないよう、ランダムに駒を配置します。このとき、はぐれルークの個数の期待値を F(n, k) と定義します。
  • 自然数 n, m に対し、1 ≦ k ≦ m の範囲の自然数 k に対する F(n, k) の和を G(n, m) と定義します。
  • 1000*G(n, m)の整数部分の値を出力してください。

方針

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の問題は解いてましたが、公開するのは今回が初めてです。
また、この機会に他の方の解答コードを見てみましたが、エレガントな解法で実装されてる方が結構いらっしゃったので驚きでした。
次はもう少し綺麗な解き方を目指すようにしないとなー。

ま、自分もまだまだ精進が必要だなーと感じ入りました。ほんと。(´Д`)