Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-22レーティングはどのように算出されているか

アルゴリズム・コンペティションにおけるレーティングのしくみ

アルゴリズム・コンペティションにおけるレーティングのしくみ - naoya_t@topcoder を含むブックマーク はてなブックマーク - アルゴリズム・コンペティションにおけるレーティングのしくみ - naoya_t@topcoder アルゴリズム・コンペティションにおけるレーティングのしくみ - naoya_t@topcoder のブックマークコメント

以下、Algorithm Competition Rating Systemからのコピペ(の拙訳)。

まとめると、参加前のレーティングから全体のスコア分布に基づいて推定されるパフォーマンスをどれだけ上回って(あるいは下回って)いるかを調べ、その差分をレーティングに重みつきで(参加歴が浅ければ大きく、長ければ小さく)反映する仕組み、といったところだろうか。

詳しくは以下を読んでほしい。

----

各々のコーダーに関する以下の統計情報が保管されている:

  • レーティング
  • 変動率(Volatility)
  • 過去にレーティングされた回数

参戦前の新規メンバーのレーティングは暫定的なものである。

コンペティションの後、参加者に対し以下のアルゴリズムが適用される。最初に、過去に参戦したことのあるメンバーのレーティングが計算される。ここでは新規参戦者のパフォーマンスは考慮されない。

次に、新規参戦者のレーティングが、コンペティション参加者全体での個々の相対的なパフォーマンスに基づいて付与される。

http://www.topcoder.com/wiki/download/attachments/4587791/Key.jpg

コーダーのハンドル名はコンペティション・アリーナ内での各々のレーティングに基づいて色付けされる

レーティングはどのように算出されているか

レーティングはどのように算出されているか - naoya_t@topcoder を含むブックマーク はてなブックマーク - レーティングはどのように算出されているか - naoya_t@topcoder レーティングはどのように算出されているか - naoya_t@topcoder のブックマークコメント

新しいレーティングは以下のように算出される:

各コンペティションの後、参加したコーダー各は以下のアルゴリズムに基づいて再レーティングされる。アルゴリズム・コンペティションでは、同じ問題セットを共有するコーダーのみが互いにレーティングされる点に留意されたい*1マラソンマッチでは、コーダーは何らかの投稿(exampleもしくはfull)をもってイベントに参加したものとみなされる。イベントに登録しただけではレーティング対象にはならない。コンペティションに参加した全員の平均レーティング(AveRating)が計算される:

http://www.topcoder.com/wiki/download/attachments/4587791/avg.gif

ここで NumCoders はコンペティションの参加コーダー数、Rating は各参加コーダーのコンペティション前の変動率を除いたレーティングを表す。

コンペティション係数(CF)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/cf.gif

ここで Volatility は参加コーダーのコンペティション前の変動率(volatility)を表す。

勝利確率(WP)推定アルゴリズム

http://www.topcoder.com/wiki/download/attachments/4587791/wp.gif

ここで Rating1 と Vol1 は比較対象となるコーダーのレーティングおよび変動率、Rating2 と Vol2 は勝利確率を計算するコーダーのレーティングおよび変動率を表す。Erf は「誤差関数*2」。

コンペティションにおいて当該コーダーが他のコーダーより高いスコアを得る確率(WPi|1≦i≦NumCOders)が推定される。

コーダーの期待ランク(ERank)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/er.gif

コーダーの期待パフォーマンス(EPerf)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/ep.gif

ここで*3は標準正規分布関数逆関数*4

各コーダーの実パフォーマンス(APref)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/ap.gif

ここで ARank はコンペティションでのスコアに基づいたコーダーの実ランク(首位なら 1、末位なら NumCoders)を表す。他のコーダーと同点の場合、同点コーダー全員によってカバーされている順位の平均値が用いられる。

コーダーのperformed asレーティング(PerfAs)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/pa.gif

コーダーにとってのコンペティションの重み(Weight)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/wt.gif

ここで 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)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/cap.gif

訳注]参加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)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/nv.gif

コーダーの新しいレーティング(NewRating)の計算:

http://www.topcoder.com/wiki/download/attachments/4587791/nr.gif

新レーティングと旧レーティングの差が Cap を超える場合、差が最大でも Cap に収まるように新レーティングが調整される。


SRM417 Div1 Easy: TemplateMatching

| 18:08 | SRM417 Div1 Easy: TemplateMatching - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM417 Div1 Easy: TemplateMatching - naoya_t@topcoder SRM417 Div1 Easy: TemplateMatching - naoya_t@topcoder のブックマークコメント

当時Div2の500点問題として解いたけどシステムテストで通らなかった問題。

1から解き直したけどそんなに難しくない。落ち着いて問題を読めば解ける。

250点問題はSTLの練習。沢山解いてスピードをつけたい。

SRM414 Div1 Easy: Embassy

| 18:08 | SRM414 Div1 Easy: Embassy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM414 Div1 Easy: Embassy - naoya_t@topcoder SRM414 Div1 Easy: Embassy - naoya_t@topcoder のブックマークコメント

formを埋めるのに必要な時間を1日の長さで割った剰余、そして開庁時間によっていくつかのパターンに分かれ・・・るけど1日の長さは高々1000000ユニットなのでBrute Forceで開始時刻を全部試せばいいじゃん・・・で解決。BruteForce万歳!

SRM413 Div1 Easy: ArithmeticProgression

| 18:08 | SRM413 Div1 Easy: ArithmeticProgression - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM413 Div1 Easy: ArithmeticProgression - naoya_t@topcoder SRM413 Div1 Easy: ArithmeticProgression - naoya_t@topcoder のブックマークコメント

テストケース全部通ればOKな感じ。解がない場合に-1を返す件について問題を読み飛ばしていてサンプルケースを見て???となっていた件

SRM412 Div1 Easy: ForbiddenStrings

| 18:08 | SRM412 Div1 Easy: ForbiddenStrings - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM412 Div1 Easy: ForbiddenStrings - naoya_t@topcoder SRM412 Div1 Easy: ForbiddenStrings - naoya_t@topcoder のブックマークコメント

Project Eulerにありそうな問題。解法は思いつくのであとはスピード。

SRM411 Div1 Easy: SentenceDecomposition

| 18:08 | SRM411 Div1 Easy: SentenceDecomposition - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM411 Div1 Easy: SentenceDecomposition - naoya_t@topcoder SRM411 Div1 Easy: SentenceDecomposition - naoya_t@topcoder のブックマークコメント

最初プライオリティキューとか駆使して探索していたが(※2つ目のコード。ちゃんと書かないと全テスト通過できないので、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;
  }
};

*1:DIV1,DIV2の区別のことか

*2:error function

*3:Φ

*4:the inverse of the standard normal function

*5:初回暫定レーティングが1200なので、Petrを抜くのに必要な最短参加回数は4回(1200→2100→2750→3275→3725)。そんな強者がいればの話だが

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20081222