ドミニオンの添付ファイル:rate.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <map>
   4 #include <cmath>
   5 #include <cstdlib>
   6 #include <sstream>
   7 #include <algorithm>
   8 #include <cmath>
   9 using namespace std;
  10 
  11 #define DISPERSION_CORRECTION 7.5
  12 
  13 // ---------- library begin ----------
  14 
  15 vector<string> split(string str, char delim)
  16 {
  17 	vector<string> ret;
  18 	for(string::size_type pos = str.find(delim); pos != string::npos; pos = str.find(delim))
  19 	{
  20 		ret.push_back(str.substr(0, pos));
  21 		str = str.substr(pos+1);
  22 	}
  23 	if(str.length() > 0)
  24 	{
  25 		ret.push_back(str);
  26 	}
  27 	return ret;
  28 }
  29 
  30 // ---------- library end ----------
  31 
  32 // ---------- structures begin ----------
  33 
  34 struct Player
  35 {
  36 	static map<string, Player> data;
  37 	string name;
  38 	double rate;
  39 	double volatility;
  40 	int playcount;
  41 	
  42 	Player() { Player(""); }
  43 	Player(string name) : name(name), rate(1500), volatility(535*DISPERSION_CORRECTION), playcount(0) {}
  44 
  45 	bool operator<(const Player& a) const
  46 	{ return rate > a.rate; }
  47 };
  48 map<string, Player> Player::data;
  49 
  50 struct Score
  51 {
  52 	string name;
  53 	double rank, point;
  54 	Score(vector<string>& args)
  55 	{
  56 		name = args[3];
  57 		if(!Player::data.count(name))
  58 			Player::data.insert(make_pair(name, Player(name)));
  59 		stringstream ss;
  60 		ss << args[4] << " " << args[5];
  61 		ss >> rank >> point;
  62 	}
  63 	Player& player() { return Player::data[name]; }
  64 };
  65 
  66 struct Game
  67 {
  68 	int id;
  69 	string date, set;
  70 	vector<Score> scores;
  71 	Game(int id) : id(id) {}
  72 	void add(vector<string>& args)
  73 	{
  74 		date = args[1];
  75 		set = args[2];
  76 		scores.push_back(Score(args));
  77 	}
  78 };
  79 
  80 struct Games : vector<Game>
  81 {
  82 	void add(vector<string> args)
  83 	{
  84 		int id;
  85 		stringstream ss;
  86 		ss << args[0];
  87 		ss >> id;
  88 		while(this->size() < id)
  89 			this->push_back(Game(this->size() + 1));
  90 		(*this)[id-1].add(args);
  91 	}
  92 
  93 	void calc(int offset = 0)
  94 	{
  95 		for(int i = offset; i < this->size(); i++)
  96 		{
  97 			Game& game = (*this)[i];
  98 			int n = game.scores.size();
  99 
 100 			// AveRating
 101 			double AveRating = 0;
 102 			for(int j = 0; j < n; j++)
 103 				AveRating += game.scores[j].player().rate;
 104 			AveRating /= game.scores.size();
 105 
 106 			// CF
 107 			double CF, CF_vol = 0, CF_rate = 0;
 108 			for(int j = 0; j < n; j++)
 109 			{
 110 				Player& p = game.scores[j].player();
 111 				CF_vol += p.volatility * p.volatility;
 112 				CF_rate += (p.rate - AveRating) * (p.rate - AveRating);
 113 			}
 114 			CF = sqrt(CF_vol / n + CF_rate / (n-1));
 115 			
 116 			// ERank EPref APref etc..
 117 			for(int j = 0; j < n; j++)
 118 			{
 119 				Score& s = game.scores[j];
 120 				Player& p = s.player();
 121 
 122 				double erank = 0.5, epref, apref, prefas, weight, cap, new_rate, new_vol;
 123 				for(int k = 0; k < n; k++)
 124 					erank += wp(game.scores[k].player(), p);
 125 				epref = - probit((erank - 0.5) / n);
 126 				apref = - probit((s.rank - 0.5) / n);
 127 				prefas = p.rate + CF * (apref - epref);
 128 				weight = 1 / (1 - (0.42/DISPERSION_CORRECTION / (p.playcount + 1) + 0.18/DISPERSION_CORRECTION)) - 1;
 129 				cap = 150 + 1500 / (p.playcount + 2);
 130 				new_rate = (p.rate + weight * prefas) / (1 + weight);
 131 				new_vol = sqrt((new_rate - p.rate)*(new_rate - p.rate) / weight + p.volatility * p.volatility / (weight + 1));
 132 				p.rate = new_rate;
 133 				p.volatility = new_vol;
 134 				p.playcount++;
 135 			}
 136 		}
 137 	}
 138 	
 139 	double erfinv(double x)
 140 	{
 141 		double r = 0;
 142 		double a[] = { 1, 1.0/12, 7.0/480, 127.0/40320, 4369.0/5806080, 34807.0/182476800 };
 143 		for(int i = 0; i < 6; i++)
 144 			r += pow(M_PI, i) * a[i] * pow(x, i*2+1);
 145 		return sqrt(M_PI) * r / 2;
 146 	}
 147 	double wp(Player p1, Player p2)
 148 	{
 149 		double a = (p1.rate - p2.rate) / sqrt(2*(p1.volatility * p1.volatility + p2.volatility * p2.volatility));
 150 		return (erf(a) + 1) / 2;
 151 	}
 152 	double probit(double x)
 153 	{
 154 		return sqrt(2) * erfinv(2*x - 1);
 155 	}
 156 };
 157 
 158 // ---------- structures end ----------
 159 
 160 int main()
 161 {
 162 	string str;
 163 	getline(cin, str); // ignore header line;
 164 	
 165 	Games games;
 166 	while(getline(cin, str))
 167 		games.add(split(str, ','));
 168 	
 169 	games.calc();
 170 
 171 	vector<Player> players;
 172 	for(map<string,Player>::iterator it = Player::data.begin(); it != Player::data.end(); ++it)
 173 		players.push_back(it->second);
 174 	sort(players.begin(), players.end());
 175 	for(int i = 0; i < players.size(); i++)
 176 		cout << players[i].name << "\t" << round(players[i].rate) << endl;
 177 }