CodeIQ：一流を見分けられるのは誰？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「一流を見分けられるのは誰？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
（前略）

今回の設問ではDCG(Discounted Cumulative Gain)と呼ばれる指標を使ってみたいと思います。

本設問で求められるプログラムの前提条件は、以下の通りとなります。

標準入力から、各アイテムの評価値（数値が大きいほど、評価が高いことを示す）が、次のように評価者の人数分複数行送られる
　（評価者1）　アイテム1の評価値 アイテム2の評価値 アイテム3の評価値 ...
　 （評価者2）　アイテム1の評価値 アイテム2の評価値 アイテム3の評価値 ...
　このとき、アイテムの順位ではなく評価値（順位とは逆で数値が大きいほど、評価が高い）が与えられることにご注意ください。
入力されるテキストの行番号を評価者の番号とみなす
評価者の人数は、3人以上5人以下とする
アイテムの数は、3個以上5個以下とする
評価値は1以上10以下の整数とし、その組み合わせは固定される
評価値はアイテムごとに異なり、重複や欠落はないものとする
アイテムの順序は、真の評価値が高い順に並んでいることを前提とする
　よって、最も望ましい評価値は5>3>1という風に単調減少する場合となる
DCG(Wikipediaへのリンク)をすべてのアイテムに適用して評価者の順位を求めること。
ここでrel iと称される関連度を示す変数にはアイテムiの評価値を、変数pにはアイテム数をそのまま用いること。
またDCGの求め方は複数提案されているが、最初に解説される下記の数式を用いること
fig.1
DCGの値が同じ評価者同士は、同じ順位とし、下の順位に合わせる。
例えば、評価者が3人で、上位2人が同じDCGの場合、2位が2名、3位が1名となる
求めた順位を評価者の番号順に、改行区切りで標準出力に送ること

以下、入力と出力例です。
入力出力
3 1 2
1 3 2
3 2 1
 2
3
1
6 10 3 1
10 3 1 6
10 3 6 1
10 3 6 1
 4
3
2
2

上記の１番目の例の場合、各評価者のDCGは、小数点第5位以下切捨てで、次のようになります。

3 + 1/log2(2+1) + 2/log2(2+2) = 4.6309
1 + 3/log2(2+1) + 2/log2(2+2) = 3.8927
3 + 2/log2(2+1) + 1/log2(2+2) = 4.7618

この数字が高いほど上位となるので、評価者の番号順に 2位 3位 1位となるわけですね。

いかがでしょうか？
一流だけを見分けるのか、一流以下のすべてを見分けるのかによって問題の複雑さがまるで変わってくることに気づかされますね。
本設問を通じて、検索エンジンやレコメンドシステムとサービスの裏側にも興味を持っていただければ幸いです。

【問題】

標準入力から、各アイテムの評価値（数値が大きいほど、評価が高いことを示す）が、評価者の人数分複数行送られます。
このとき評価されるアイテムの順序は、真の評価値が高い順に並んでいることを前提とした上で、順位付け問題の精度評価指標であるDCGを用いて各評価者の順位を求め、その結果を標準出力に返してください。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def dcg(arr)
	ret = arr[0].to_f

	for i in 1...arr.size
		ret += arr[i] / (Math.log2(i+1+1))
	end

	return ret
end

def rank(arr)
	ret = {}
	arr.sort.each_with_index{|v, i|
		next if ret[v] != nil
		ret[v] = arr.size - i
	}
	return ret
end

# main
res = []
while line = gets
	line.strip!
	next if line.empty?

	vals = line.split.map{|v| v.to_i}
	res << dcg(vals)
end

rk = rank(res)

res.each{|v|
	p rk[v]
}

解説

問題の通りに実装するだけです。

考え方

素直に問題に示された式通りに実装すればOKです。

main

入力値を1行ずつ読み取りながら数値にしてdvg()に渡し、計算結果を得ます。
それをrank()で順位づけして各行の順位を印字します。

dcg(arr)

DCGを計算します。
引数arrは入力値の1行を数値の配列にしたものです。
問題で示された式をそのまま実装しただけなので説明は省きます。

rank(arr)

引数arrは各行のDCGの計算結果が入った配列です。
これに順位づけし{DCGの計算結果 => 順位}の連想配列にします。
順位はarrをソートしたものを順番に見ると、arr.size - iです。同じ順位は低い方の値に合わすのでret[v]がすでにあれば無視します。

雑感

問題の通りに実装するだけなので難しくありません。 順位づけが面倒臭いです。