TopCoderの点数と時間の関係をグラフで表す

競技プログラミングTopCoderでは、解いた時間の速さに応じて点数が決まる。こちらで時間から点数を計算する式が示されているので、逆に点数から自分が回答にかかった時間を計算するために、Rで関数を書いてみることにした。

TimeToPoint <- function(x,mP,mT){
 mP*(0.3+(0.7*mT^2)/(10*x^2+mT^2))
}

timeNeeded <- function(p,maxPts=250,maxTime=75){
 res <- uniroot(function(x){TimeToPoint(x,mP=maxPts,mT=maxTime)-p},interval=c(0,maxTime))$root
}
result <- timeNeeded(p=237.93)
result

Rのインタプリタ上で上記コードを実行すると、timeNeeded関数に237.93点を与えた場合、resultには6.455(分)という解くのにかかった時間が代入される。

以下コードの解説。

timeNeeded関数の引数はpが獲得した点数、maxPtsがある問題の点数の最大値、maxTimeが解くのに使える時間の最大値である。デフォルトではmaxPtsに250、maxTimeに75(TopCoderにおけるコーディングの時間)を入れてある。必要に応じて変更する。TimeToPointはその名の通り、時間から点数を計算する関数である。

unirootは方程式の根を求める関数である。オプションのintervalで根が存在する範囲を指定する。返り値はリスト形式になっていて、rootが根に相当する。TopCoderの時間と得点の関係は単調減少にあるので、得点を与えれば、一意に点数が定まる。なお、uniroot関数で根を求める方法にはニュートン法が利用されているそうなので、intervalで指定した範囲に複数の解がある場合には利用を避けた方がよいだろう。ニュートン法は区間interval内に複数の根があったとしても、1つの根しか示してくれないからである。

最後に、問題文を開いてから回答までに消費した時間と点数の関係をグラフにする。TimeToPointは既に示した点数と消費時間の関係を表す曲線を描く関数である。

usedTime <- seq(from=0,to=75,by=0.1)
plot(usedTime,TimeToPoint(usedTime,250,75),xlim=c(0,80),ylim=c(75,250),
     xlab="Time",ylab="pts",main="TopCoder",type="l")