2008-12-22レーティングはどのように算出されているか
アルゴリズム・コンペティションにおけるレーティングのしくみ
以下、Algorithm Competition Rating Systemからのコピペ（の拙訳）。
まとめると、参加前のレーティングから全体のスコア分布に基づいて推定されるパフォーマンスをどれだけ上回って（あるいは下回って）いるかを調べ、その差分をレーティングに重みつきで（参加歴が浅ければ大きく、長ければ小さく）反映する仕組み、といったところだろうか。
詳しくは以下を読んでほしい。
----
各々のコーダーに関する以下の統計情報が保管されている：
- レーティング
- 変動率（Volatility）
- 過去にレーティングされた回数
参戦前の新規メンバーのレーティングは暫定的なものである。
コンペティションの後、参加者に対し以下のアルゴリズムが適用される。最初に、過去に参戦したことのあるメンバーのレーティングが計算される。ここでは新規参戦者のパフォーマンスは考慮されない。
次に、新規参戦者のレーティングが、コンペティション参加者全体での個々の相対的なパフォーマンスに基づいて付与される。
コーダーのハンドル名はコンペティション・アリーナ内での各々のレーティングに基づいて色付けされる
レーティングはどのように算出されているか
新しいレーティングは以下のように算出される：
各コンペティションの後、参加したコーダー各は以下のアルゴリズムに基づいて再レーティングされる。アルゴリズム・コンペティションでは、同じ問題セットを共有するコーダーのみが互いにレーティングされる点に留意されたい*1。マラソンマッチでは、コーダーは何らかの投稿（exampleもしくはfull）をもってイベントに参加したものとみなされる。イベントに登録しただけではレーティング対象にはならない。コンペティションに参加した全員の平均レーティング（AveRating）が計算される：
ここで NumCoders はコンペティションの参加コーダー数、Rating は各参加コーダーのコンペティション前の変動率を除いたレーティングを表す。
コンペティション係数（CF）の計算：
ここで Volatility は参加コーダーのコンペティション前の変動率（volatility）を表す。
勝利確率（WP）推定アルゴリズム：
ここで Rating1 と Vol1 は比較対象となるコーダーのレーティングおよび変動率、Rating2 と Vol2 は勝利確率を計算するコーダーのレーティングおよび変動率を表す。Erf は「誤差関数*2」。
コンペティションにおいて当該コーダーが他のコーダーより高いスコアを得る確率（WPi|1≦i≦NumCOders）が推定される。
コーダーの期待ランク（ERank）の計算：
コーダーの期待パフォーマンス（EPerf）の計算：
各コーダーの実パフォーマンス（APref）の計算：
ここで ARank はコンペティションでのスコアに基づいたコーダーの実ランク（首位なら 1、末位なら NumCoders）を表す。他のコーダーと同点の場合、同点コーダー全員によってカバーされている順位の平均値が用いられる。
コーダーのperformed asレーティング（PerfAs）の計算：
コーダーにとってのコンペティションの重み（Weight）の計算：
ここで TimesPlayed はコーダーがこれまでにレーティングを受けた回数を表す。高レーティングのメンバーを安定させるため、レーティングが2000〜2500のメンバーのウェイトは10%減、レーティング2500超のメンバーのウェイトは20%減とする。
［訳注］参加0回→1.5, 1回→0.6393, 2回→0.47, 3回→0.3986, 4回→0.3587, 5回→0.3333, ... 20回→0.25, ... →9/41=0.21951に収束
変動上限（Cap）の計算：
［訳注］参加0回→900, 1回→650, 2回→525, 3回→450, 4回→400, 5回→364.28, 6回→337.5, 7回→316.6, 8回→300, ... 13回→250, 28回→200, ... →150に収束。*5
コーダーの新しい変動率（NewVolatility）の計算：
コーダーの新しいレーティング（NewRating）の計算：
新レーティングと旧レーティングの差が Cap を超える場合、差が最大でも Cap に収まるように新レーティングが調整される。
SRM417 Div1 Easy: TemplateMatching
当時Div2の500点問題として解いたけどシステムテストで通らなかった問題。
１から解き直したけどそんなに難しくない。落ち着いて問題を読めば解ける。
250点問題はSTLの練習。沢山解いてスピードをつけたい。
SRM414 Div1 Easy: Embassy
formを埋めるのに必要な時間を１日の長さで割った剰余、そして開庁時間によっていくつかのパターンに分かれ・・・るけど１日の長さは高々1000000ユニットなのでBrute Forceで開始時刻を全部試せばいいじゃん・・・で解決。BruteForce万歳！
SRM413 Div1 Easy: ArithmeticProgression
テストケース全部通ればOKな感じ。解がない場合に-1を返す件について問題を読み飛ばしていてサンプルケースを見て？？？となっていた件
SRM411 Div1 Easy: SentenceDecomposition
最初プライオリティキューとか駆使して探索していたが（※２つ目のコード。ちゃんと書かないと全テスト通過できないので、250点にしては難しめでは？と思ったけど）これはDPで書くと超簡単に解ける例。
DP、というか再帰とメモ化で解けるパターンを見つける練習が必要。
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
string strsort(const string &str) {
vector<char> buf(all(str));
sort(all(buf));
string sorted(all(buf));
return sorted;
}
class SentenceDecomposition {
private:
int score(string orig, string word) {
if (strsort(orig) != strsort(word)) return -1;
int d = orig.length();
for (int i=d-1; i>=0; i--) if (orig[i] == word[i]) d--;
return d;
}
public:
int len;
string sent;
vector<string> valids;
vector<int> memo;
int sub(int len) {
if (len==0) return 0;
if (memo[len] < INT_MAX) return memo[len];
int min_score = INT_MAX;
tr(valids,it) {
int vl = it->length(); if (vl > len) continue;
int subsc = sub(len-vl); if (subsc == INT_MAX) continue;
int sc = score(*it,sent.substr(len-vl,vl)); if (sc == -1) continue;
sc += subsc; if (sc < min_score) min_score = sc;
}
memo[len] = min(memo[len], min_score);
return min_score;
}
int decompose(string sentence, vector<string> validWords) {
sent = sentence; len = sentence.length();
valids = validWords;
memo.resize(len+1); fill(all(memo),INT_MAX);
int topscore = sub(len);
return (topscore == INT_MAX)? -1 : topscore;
}
};
以下、最初に書いたコード。このコードで（何度か修正した末）システムテストも全て通るようになったが、TopCoderの統計情報を見たらこの問題はDPに分類されているので、書き直して上のコードになった。
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
bool greater_by_length(const string& s1, const string& s2 )
{
return s1.length() > s2.length();
}
template <typename T> struct better : binary_function<T,T,bool> {
bool operator()(const T& X, const T& Y) const{
// at, score
if (X.first >= Y.first) return X.second < Y.second;
return false;
}
};
string strsort(const string &str) {
vector<char> buf(all(str));
sort(all(buf));
string sorted(all(buf));
return sorted;
}
class SentenceDecomposition {
private:
bool abc[26];
bool usable(const string &str) {
rep(i,str.length()) if (!abc[str[i]-'a']) return false;
return true;
}
int score(string orig, string word) {
int d = orig.length();
for (int i=d-1; i>=0; i--) if (orig[i] == word[i]) d--;
return d;
}
public:
int decompose(string sentence, vector<string> validWords) {
int l=sentence.length();
rep(i,26) abc[i] = false;
rep(i,l) abc[sentence[i]-'a'] = true;
set<string> s;
tr(validWords,wt) if (usable(*wt)) s.insert(*wt);
vector<string> valids(all(s));
sort(all(valids),greater_by_length);
int n=valids.size();
vector<string> words(n);
rep(i,n) {
words[i] = strsort(valids[i]);
}
priority_queue<pair<int,int>, vector<pair<int,int> >, better<pair<int,int> > > pq;
vector<int> said(l+1,INT_MAX);
rep(i,n) {
int wl = words[i].length();
if (0+wl <= l) {
string ss = sentence.substr(0,wl);
if (strsort(ss) == words[i]) {
int sc = score(valids[i],ss);
if (sc < said[wl]) {
pair<int,int> p = make_pair(wl,sc);
pq.push(p);
said[wl] = sc;
}
}
}
}
int topscore = INT_MAX;
while (!pq.empty()) {
int at = pq.top().first, pt = pq.top().second;
pq.pop();
if (at == l) {
topscore = min(topscore,pt);
continue;
}
rep(i,n) {
int wl = words[i].length();
if (at+wl <= l) {
string ss = sentence.substr(at,wl);
if (strsort(ss) == words[i]) {
int newscore = pt+score(valids[i],ss);
if (newscore < topscore) {
if (newscore < said[at+wl]) {
pair<int,int> p = make_pair(at+wl,newscore);
pq.push(p);
said[at+wl] = newscore;
}
}
}
}
}
}
return (topscore == INT_MAX)? -1 : topscore;
}
};