Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@key-moon
Last active August 24, 2020 15:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save key-moon/e4805b2eeb4ddf7cb3b04b9dd9203f30 to your computer and use it in GitHub Desktop.
Save key-moon/e4805b2eeb4ddf7cb3b04b9dd9203f30 to your computer and use it in GitHub Desktop.
AtCoderからのデータ取得周りは外部の自作ライブラリに依存してるのでこれ単体では動かないです
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