AtCoderからのデータ取得周りは外部の自作ライブラリに依存してるのでこれ単体では動かないです
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.IO; | |
using System.Linq; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using Newtonsoft.Json; | |
using System.Threading.Tasks; | |
using AngleSharp.Html; | |
namespace AtCoder | |
{ | |
class Program | |
{ | |
const int DebugLevel = 1; | |
static void Main(string[] args) | |
{ | |
for (int id = 173; id >= 126; id--) | |
{ | |
Console.WriteLine($"start calc abc{id}..."); | |
const int PROBLEM_COUNT = 6; | |
const int CONTEST_TIME = 100; | |
string fstRow = $",{string.Join(",", Enumerable.Range(1, CONTEST_TIME))}\n"; | |
string paperRes = fstRow; | |
string propRes = fstRow; | |
for (int i = 0; i < PROBLEM_COUNT; i++) | |
{ | |
Console.WriteLine($"start calc problem[{i}]..."); | |
List<double> paperDiffs = new List<double>(); | |
List<double> propDiffs = new List<double>(); | |
Console.Write($"|{string.Join("", Enumerable.Repeat('-', CONTEST_TIME))}|\n "); | |
for (int t = 60; t <= CONTEST_TIME * 60; t += 60) | |
{ | |
paperDiffs.Add(PredictDifficulty($"abc{id}", i, thresholdSec: t, method: 0)); | |
propDiffs.Add(PredictDifficulty($"abc{id}", i, thresholdSec: t, method: 1)); | |
Console.Write('#'); | |
} | |
Console.WriteLine(); | |
paperRes += $"{i},{string.Join(",", paperDiffs)}\n"; | |
propRes += $"{i},{string.Join(",", propDiffs)}\n"; | |
} | |
File.WriteAllText($@"~\res\abc{id}.csv", paperRes + propRes); | |
} | |
} | |
static double PredictDifficulty(string contestID, int problemInd, int thresholdSec = int.MaxValue, int thresholdRate = 5000) | |
{ | |
var data = GetData(contestID, true).Where(x => x.IsRated).ToArray(); | |
data = data.Select(x => | |
{ | |
var res = x; | |
res.Time = x.Time.Select(x => x is null || thresholdSec < x.Value ? null : x).ToArray(); | |
return res; | |
}).ToArray(); | |
var d = data | |
.Where(x => !(x.APerf is null || thresholdRate < x.APerf || x.Time[problemInd] is null)) | |
.Select(x => ((double)x.APerf.Value, (double)x.Time[problemInd].Value)).ToArray(); | |
return PaperPredictor(d); | |
return ProposedPredictor(d); | |
static double PaperPredictor((double aperf, double time)[] data) | |
{ | |
int n = data.Length; | |
const int DIFF_MIN = -1000; | |
const int DIFF_MAX = 5000; | |
double maxL = double.NegativeInfinity; | |
int maxDiff = -1; | |
double t = double.NaN; | |
for (int diff = DIFF_MIN; diff < DIFF_MAX; diff++) | |
{ | |
var probs = data.Select(x => 1 / (1 + Math.Pow(6, (diff - x.aperf) / 400))).ToArray(); | |
var T = data.Zip(probs, (x, prob) => x.time * prob).Sum() / n; | |
var likelihood = probs.Sum(x => Math.Log(x)) - n * Math.Log(T) - n; | |
if (maxL < likelihood) | |
{ | |
maxL = likelihood; | |
t = T; | |
maxDiff = diff; | |
} | |
} | |
if (1 <= DebugLevel) Console.WriteLine($"L(f_{{{maxDiff:0},{t:0.00}}}) -> {maxL}"); | |
return maxDiff; | |
} | |
double ProposedPredictor((double aperf, double time)[] data) | |
{ | |
int N = data.Length; | |
int End = 100 * 60; | |
double logEnd = Math.Log(End); | |
const double C = 350.671248852759; //200 * Math.PI * Math.Log(Math.E, 6); | |
const double CInv = 1 / C; | |
double[] logTs = data.Select(x => Math.Log(x.time)).ToArray(); | |
double logTSum = logTs.Sum(); | |
var constLTerm = N * Math.Log(Math.Sqrt(2 * Math.PI)) + logTSum; | |
//対数尤度関数の偏微分の2次方程式の各項 | |
var a = -C * N; | |
double c = C * logTs.Sum(logT => (logT - logEnd) * (logT - logEnd)); | |
const int DIFF_MIN = -1000; | |
const int DIFF_MAX = 2500; | |
double maxL = double.NegativeInfinity; | |
int maxDiff = -1; | |
double maxSigma = -1; | |
for (int diff = DIFF_MIN; diff < DIFF_MAX; diff += 1) | |
{ | |
var b = data.Select(x => x.aperf).Zip(logTs, (rate, logT) => (rate - diff) * (logT - logEnd)).Sum(); | |
var D = Math.Sqrt(b * b - 4 * a * c); | |
if (double.IsNaN(D)) continue; | |
List<double> sCand = new List<double>(); | |
var s1 = (-b + D) / (2 * a); | |
var s2 = (-b - D) / (2 * a); | |
if (0 <= s1) sCand.Add(s1); | |
if (0 <= s2) sCand.Add(s2); | |
//これらについては|s2|,|s1|であり、結果は変わらないので計算しないことにする。 | |
//var s3 = (b + D) / (2 * a); | |
//var s4 = (b - D) / (2 * a); | |
//if (s3 <= 0) sCand.Add(s3); | |
//if (s4 <= 0) sCand.Add(s4); | |
double calcLikelihood(double sigma) | |
{ | |
static double calcSingleL(double sigma, double diff, double maxTime, double rate, double time) | |
{ | |
var logT = Math.Log(time); | |
var tmp = logT - Math.Log(maxTime) - sigma / C * (diff - rate); | |
return -Math.Log(Math.Sqrt(2 * Math.PI) * sigma) - logT - tmp * tmp / (2 * sigma * sigma); | |
} | |
//return data.Sum(x => calcSingleL(sigma, diff, End, x.aperf, x.time)); | |
sigma = Math.Abs(sigma); | |
var sigmaPerC = sigma * CInv; | |
var term = 0.0; | |
foreach (var (rate, time) in data) | |
{ | |
var tmp = Math.Log(time) - logEnd - sigmaPerC * (diff - rate); | |
term += tmp * tmp; | |
} | |
term /= 2 * sigma * sigma; | |
var res = -(constLTerm + N * Math.Log(sigma) + term); | |
if (2 <= DebugLevel) Console.WriteLine($"L(f_{{{diff:0},{sigma:0.000}}}) -> {res:0.0}"); | |
return res; | |
} | |
foreach (var s in sCand) | |
{ | |
var l = calcLikelihood(s); | |
if (maxL < l) | |
{ | |
maxL = l; | |
maxDiff = diff; | |
maxSigma = s; | |
} | |
} | |
} | |
if (1 <= DebugLevel) Console.WriteLine($"L(f_{{{maxDiff:0},{maxSigma:0.000}}}) -> {maxL:0.0}"); | |
return maxDiff; | |
} | |
} | |
static Dictionary<string, Row[]> cache = new Dictionary<string, Row[]>(); | |
static Row[] GetData(string contestID, bool useCache = false) | |
{ | |
if (useCache && cache.ContainsKey(contestID)) return cache[contestID]; | |
Standings standings = Standings.GetStandings(contestID, useCache); | |
var screenNames = standings.TaskInfo.Select(x => x.TaskScreenName).ToArray(); | |
var aperfs = Scraping.GetAPerfs(contestID, useCache); | |
var standingsData = standings.StandingsData.Select(x => new Row() | |
{ | |
ScreenName = x.UserScreenName, | |
IsRated = x.IsRated, | |
APerf = aperfs.ContainsKey(x.UserScreenName) ? (long?)aperfs[x.UserScreenName] : null, | |
Time = screenNames.Select(y => x.TaskResults.ContainsKey(y) && x.TaskResults[y].Elapsed != 0 ? (long?)(x.TaskResults[y].Elapsed / 1000000000) : null).ToArray() | |
}).ToArray(); | |
if (!cache.ContainsKey(contestID)) cache.Add(contestID, null); | |
return cache[contestID] = standingsData; | |
} | |
static void Save(string contestID) | |
{ | |
var standingsData = GetData(contestID); | |
StreamWriter streamWriter = new StreamWriter($@"C:\Users\akikuchi\Documents\notebook\data\{contestID}.csv"); | |
foreach (var item in standingsData) | |
{ | |
streamWriter.WriteLine($"{item.ScreenName},{item.IsRated},{item.APerf},{string.Join(",", item.Time)}"); | |
} | |
streamWriter.Dispose(); | |
} | |
struct Row | |
{ | |
public string ScreenName; | |
public bool IsRated; | |
public long? APerf; | |
public long?[] Time; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment