AtCoderでユーザーおよび問題をイロレーティングで評価してみた

# 概要
　それは、数日前の**[chokudaiさん(AtCoder社長)のツイート](https://twitter.com/chokudai/status/695206697137102848)**に遡ります。「コンテスト結果から自動的に問題難易度を推測するようなシステム」ということで、とりあえず**ABC(AtCoder Beginner Contest)の結果からレーティングを構築**してみることにしました。もちろん[AtCoderだとアカウントごとに級位＋レーティング値が表示](https://twitter.com/atcoder/status/259655540530114560)されますが、アレだと1級以上でないとレーティング値にならないもので……。

**※実際のコード(Rubyで実装)は文末にまとめて記述しています。**

# 実装
## とりあえずデータをクロールする
　以前、[AtCoderでユーザー名から解いた問題を検索するシステム](http://qiita.com/YSRKEN/items/8f0081da7d92dfa7be3c)を作りましたので、それをちょっと弄れば**各コンテスト毎に誰がどの問題に挑戦してAC/その他したか**を収集できます。長時間のアクセスになりますので、[chokudai博士お許し下さい](http://dic.nicovideo.jp/a/%E3%83%9C%E3%83%AB%E3%82%AC%E5%8D%9A%E5%A3%AB)……。

## イロレーティングで結果を評価する
　イロレーティングについて、詳しくは[Wikipediaでも見ればいい](https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%AD%E3%83%AC%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0)と思いますが、要するに**レーティングの値をやり取りすることで強さを表現する**手法のことです。実際の実装では、イロレーティングの実装をそのまま持ってきて、変動部分は小数点以下切り捨てにしました(つまり、常にレーティングが整数になる)。
　ここでどうやって勝敗を決めるかですが、とりあえず**「コンテストXの問題に1つでも触れた者全てについて、問題YがACできていればユーザの勝ち、そうでなければユーザの負け」**としました。例えばABC001のB問題だけACしていると、「ABC001のA・C・D問題については解いていないので負け、B問題については解いているので勝ち」となります。当然ですが、このロジックでは、問題自身もレーティングの対象となります。
　なお、1周しただけではレーティングの変動が収まっていませんので反復させますが、**「1周した際に起きたすべてのレーティングの変動合計」が変化しなかった時**を平衡状態として扱い、反復を終了させる実装にしています。

# 結果
　まず問題についてのレーティング値を貼ります。表の中では、問題A～Dについてレーティングが最も高かったものと低かったものを強調しています。
[問題Aで最易](http://abc001.contest.atcoder.jp/tasks/abc001_1)　[問題Aで最難](http://abc022.contest.atcoder.jp/tasks/abc022_a)
[問題Bで最易](http://abc016.contest.atcoder.jp/tasks/abc016_2)　[問題Bで最難](http://abc027.contest.atcoder.jp/tasks/abc027_b)
[問題Cで最易](http://abc012.contest.atcoder.jp/tasks/abc012_3)　[問題Cで最難](http://abc008.contest.atcoder.jp/tasks/abc008_3)
[問題Dで最易](http://abc028.contest.atcoder.jp/tasks/abc028_d)　[問題Dで最難](http://abc025.contest.atcoder.jp/tasks/abc025_d)

|No.|Q.|rate|No.|Q.|rate|No.|Q.|rate|No.|Q.|rate|
|:--|:--|--:|:--|:--|--:|:--|:--|--:|:--|:--|--:|
|**1**|**A**|**681**|9|A|996|17|A|1028|25|A|1048|
|1|B|1218|9|B|1227|17|B|1323|25|B|1213|
|1|C|1875|9|C|2230|17|C|2055|25|C|2224|
|1|D|2013|9|D|2327|17|D|2207|**25**|**D**|**2604**|
|2|A|989|10|A|882|18|A|1093|26|A|873|
|2|B|1139|10|B|1170|18|B|1308|26|B|1247|
|2|C|1386|10|C|1392|18|C|2092|26|C|1781|
|2|D|1917|10|D|2113|18|D|2093|26|D|1863|
|3|A|973|11|A|1010|19|A|1009|27|A|971|
|3|B|1390|11|B|1308|19|B|1470|**27**|**B**|**1659**|
|3|C|1514|11|C|1664|19|C|1654|27|C|2072|
|3|D|2289|11|D|2159|19|D|1768|27|D|2214|
|4|A|942|12|A|1025|20|A|978|28|A|930|
|4|B|1264|12|B|1205|20|B|1036|28|B|1232|
|4|C|1447|**12**|**C**|**1251**|20|C|2076|28|C|1346|
|4|D|2210|12|D|1726|20|D|2438|**28**|**D**|**1541**|
|5|A|978|13|A|1022|21|A|1011|29|A|833|
|5|B|1139|13|B|1223|21|B|1340|29|B|1088|
|5|C|1602|13|C|1994|21|C|2003|29|C|1459|
|5|D|1898|13|D|2046|21|D|2055|29|D|1983|
|6|A|986|14|A|1120|**22**|**A**|**1177**|30|A|1008|
|6|B|1581|14|B|1537|22|B|1352|30|B|1576|
|6|C|1784|14|C|1764|22|C|2008|30|C|1771|
|6|D|1978|14|D|2097|22|D|2130|30|D|1971|
|7|A|939|15|A|918|23|A|904|31|A|852|
|7|B|1175|15|B|1091|23|B|1512|31|B|1044|
|7|C|1779|15|C|1664|23|C|2133|31|C|2007|
|7|D|2116|15|D|1798|23|D|2118|31|D|2202|
|8|A|903|16|A|936|24|A|1054|32|A|968|
|8|B|1516|**16**|**B**|**983**|24|B|1268|32|B|1524|
|**8**|**C**|**2266**|16|C|1767|24|C|1711|32|C|1813|
|8|D|2359|16|D|1889|24|D|2287|32|D|1985|

　次に、レーティングトップ10のスコアを貼ります(ABC全体で5971名)。参考にしてみてください。**ちなみに私はrate1477の3172位なので雑魚です。**

|rank|ユーザ名|rate|
|--:|:--|--:|
|1|紙ぺーぱー|3194|
|2|pekempey|3189|
|3|ricky|3080|
|4|airis|3039|
|5|chabo|3037|
|6|りあん|3029|
|7|mamekin|3023|
|8|omu|3018|
|9|127_kimiyuki|3011|
|10|ヘクト(あずさ)|3007|

　そして、分布のヒストグラムを乗せておきます。レート2250以上は、上位10％未満の競プロガチ勢であると推測されますね。
(まあこれはABCの結果ですので、ARCの結果も後日載せます)
![hist.png](https://qiita-image-store.s3.amazonaws.com/0/29802/5f0d5b06-cbd2-1b13-9d89-baf5b2df0717.png)


# おまけ(ソースコード)
　クロール用・レーティング計算用となっております。

```download.rb
require 'nokogiri'
require 'open-uri'
output = ''
query_list = ['A', 'B', 'C', 'D']
1.upto(32){|n|
	name_list = {}
	ac_name_list = {}
	1.upto(0/0.0){|page|
		url = "http://abc#{sprintf('%03d', n)}.contest.atcoder.jp/submissions/all/#{page}"
		charset = nil
			html = open(url){|f|charset=f.charset;f.read}
			doc = Nokogiri::HTML.parse(html, nil, charset)
			nodes = doc.css('table[class="table table-bordered table-striped table-wb"] > tbody > tr')
			break if nodes.size == 0
			puts "#{n} #{page} #{nodes.size}"
			nodes.each{|node|
				query = (node.css('td > a')[0].inner_text)[0]
				name = node.css('td > a')[1].inner_text
				result = node.css('td > span').inner_text
				name_list[name] = 1
				if result == 'AC' then
					ac_name_list[query] = Hash.new(0) unless ac_name_list.has_key?(query)
					ac_name_list[query][name] = 1
				end
			}
	}
	name_list.keys.each{|name|
		query_list.each{|query|
			output += "#{n}_#{query},#{name},#{(ac_name_list[query][name] == 1 ? 'Win' : 'Lose')}\n"
		}
	}
}
File.write('log.txt', output)
```

```calc.rb
user_list = {}
result_list = {}
File.read('log.txt', :encoding => Encoding::UTF_8).split("\n").each{|line|
	temp = line.split(',')
	user_list[temp[0]] = 1500
	user_list[temp[1]] = 1500
	if temp[2] == 'Win' then
		result_list[[temp[0], temp[1]]] = true
	else
		result_list[[temp[0], temp[1]]] = false
	end
}
sum_pt_ = 0
1000.times{|i|
	sum_pt = 0
	result_list.each{|pair, result|
		user_a = pair[0]
		user_b = pair[1]
		r_a = user_list[user_a]
		r_b = user_list[user_b]
		e_a = 1.0 / (1.0 + 10**(1.0 * (r_b - r_a) / 400))
		e_b = 1.0 - e_a
		if result then
			move_pt = (32 * (0.0 - e_a)).to_i
			user_list[user_a] += move_pt
			user_list[user_b] -= move_pt
			sum_pt += move_pt.abs
		else
			move_pt = (32 * (0.0 - e_b)).to_i
			user_list[user_a] -= move_pt
			user_list[user_b] += move_pt
			sum_pt += move_pt.abs
		end
	}
	puts "#{i+1} #{1.0 * sum_pt / user_list.size}"
	break if sum_pt == sum_pt_
	sum_pt_ = sum_pt
}
output = ''
user_list.sort_by{|key,val| -val}.each{|user, rating|
	output << "#{user}\t#{rating}\n"
}
File.write('rating.txt', output)
```