RでYahoo Japanの株価データにアクセスする
昔はPerlでパーサを書いて取得したりしたんですが、最近はRに便利なパッケージがあってほぼコマンド一つで株価データにアクセスできるようです。
> install.packages("quantmod", dependencies = TRUE)
> library("quantmod")
まずquantmodのパッケージをインストールしてロードします。
> getSymbols("998407", src="yahooj")
これで日経先物のデータがData Frameに入ります。他にもソースを変えればGoogleとかも。
> getSymbols("goog", src="yahoo")
適当にARIMAモデルで予測してみるとこんな感じ。
Point Forecast Lo 80 Hi 80 Lo 95 Hi 95
288.71 526.4316 505.2486 547.6146 494.0351 558.8282
288.86 526.4608 496.5036 556.4181 480.6452 572.2765
289.00 526.4900 489.8001 563.1800 470.3776 582.6025
289.14 526.5193 484.1533 568.8852 461.7262 591.3124
289.29 526.5485 479.1819 573.9150 454.1076 598.9894
289.43 526.5777 474.6902 578.4652 447.2227 605.9327
289.57 526.6069 470.5620 582.6518 440.8937 612.3201
289.71 526.6361 466.7216 586.5506 435.0048 618.2674
289.86 526.6653 463.1164 590.2142 429.4757 623.8550
290.00 526.6946 459.7081 593.6810 424.2477 629.1414
290.14 526.7238 456.4678 596.9797 419.2766 634.1710
290.29 526.7530 453.3730 600.1329 414.5280 638.9779
290.43 526.7822 450.4059 603.1585 409.9748 643.5896
290.57 526.8114 447.5520 606.0708 405.5946 648.0282
AtCoder Regular Contest 072 E - Alice in linear land
はじめ距離0にいて目的地が距離Dのところにある。計画{d1, d2, ..., dN}があって、i回目の行動でd[i]進んだとき、現在地点よりも目的地に近くなるならばその方向に進む。通り過ぎた場合は折り返しもあり。この計画のqj番目を書き換えて目的地にゴール出来ないようにすることはできるか？
i番目の行動をした時に、その後の行動をしたときに目的地にたどり着けない最小の距離をdpで求める。このdpはdp[N]が1(残りの行動がない場合、ゴールできる可能性があるのはDの上にいる場合のみ)として後ろから更新できる。また最小の距離を求めているので、この数列は単調増加になる。
次にi番目まで行動した時の位置を前もって計算しておく。この時、行動のi番目を書き換えるとは、i-1番目まで行動が終わった位置からゴールまでの任意の位置に移動させることで目的地につかないようにできるか？という問題になる。
よって答えは、dpで求めたi番目の値が、i-1番目までの行動結果の位置よりも小さい場合、dpで求めた位置に移動するように書き換えることによってゴールできないようにすることができる。
逆の場合、距離が大きくなる方向へは移動できないので必ずゴールできてしまう。
折り返しとかがあるので、絶対値のdpで求める。
Yukicoder Contest 161
よくある数字を加減乗除した時の最大値を求める問題…であるが本番解けず。Nが小さいので思わず全探索してしまったがTLEする。変な貪欲をやってみたがもちろん合わず。
正しい方法はi項目まで使った時の最小値及び最大値を持ってdpする。最初の1項目は+限定なのに注意。
本番時間切れ。よくある格子座標の組み合わせをdpで求めるやつ。これをK, Pの全組み合わせでやる。O(HW 2^K)
No.507 ゲーム大会(チーム決め) - yukicoder
K君除いた他の人をスコアでソートし、インデックスを二分探索。
二分探索中の仮indexがxであるとき、K君のスコア+a[x] + 1以上のスコアになるペアの最大数を計算。これはスコア最大値の人が、そのスコアを超えるような最低の人とペアになるようにすればよい。配列aのコピーが大量に発生する系の問題苦手。
AtCoder Regular Contest 062 - E - AtCoDeerくんと立方体づくり
正方形がN個(N≦400)与えられ、それぞれの正方形の四隅には異なる色C[i,j] (C[i, j]≦999)がついている。この正方形を6個使って立方体を作るとき、隅の色を合わせる組み合わせは何通りあるか。ただし、回転したものは同一のものとみなす。
方針はすぐ立つ。まず1個の面を方向を含めて1個固定、対面の面を回転を含めて4通り考える。こうすると側面に置きべき色が決定されるので、その組み合わせをカウントすればよい。これだけ書くと簡単であるが、カウントするためのデータ構造が複雑。
まず正方形に対し、回転を同一視したハッシュ関数を用意する。例えば数値をくっつけて単純ハッシュにしたもののうち、回転させた場合の最小値など。これで次のMapを作成。
map1[ハッシュ] = ハッシュ値の正方形の数
map2[ハッシュ]=このハッシュ値を持つ正方形が回転したときにまた同じ形になる組み合わせ。1,2,4のいずれかの値
次に前後が決められて、4隅の色が決まった状態でその4隅のハッシュを計算し、ret *= map1[hash] * map2[hash] などという計算をする。その後 map1[hash]をデクリメントして次の面の組み合わせを同様に計算する。
もちろん次の前後の面の組み合わせに行くときには引いたりしたmap1を元に戻す必要がある。あと、確認の最初は既に使用済みの前後の面のぶんをmap1からデクリメントしておくのを忘れないようにしたい。
計算量はO(N^2 logN)なのであるが、その中に16回のループがあり、しかもmapの初期化等が入るので定数倍が重い。
New Year Contest 2015 C - 文字列の書き換え
文字列が2個与えられる。任意の場所に直前の文字と違う任意の文字を挿入という操作を繰り返すとき、与えられた最初の文字列を2番めの文字列に変換できるか？
文字を追加していくと考えると、最後の文字にだけ依存する条件なのでそういったdpを構成する。
dp[i][j] をsのi文字目までのprefixからtのj文字目までのprefixが生成できるかをbooleanで持つdpテーブルとする。例えばsnukeのprefixであるsnuからsnuuが生成できるか？など。
もちろんi>jの場合は常にfalseである。dpの更新は次の2通り
- dp[i][j]がtrue、かつsのi+1文字目とtのj+1文字目が同じであればdp[i + 1][j + 1]もtrue
- 上記の条件かつtのi+1文字目がtのi + 2文字目と違うのであればdp[i][k] (k >=j) はすべてtrue
1番目は単に文字が一致してた時の話。2番目が少しわかりにくいが結局同じ文字が2個最後に並んでいるような状況でなければ任意の文字列が構成できるという話。(実験すればすぐわかる)
逆にこれ以外はfalseのまま。O(N^2)
IRT + Stan でらくらくスコアリング
テスト問題を作成する時に困るのが配点です。できれば問題の難易度に応じて配点を決めたいのですが、問題の難易度の推定は意外と難しいです。そこでTOEICなんかではIRTという方法が使われています。
数理モデルはWikipeida当たりに詳しいのでそちらを参考にしてください。
簡単にいえば、能力の高い人ほど難易度の難しい問題が解ける確率が上がる、というモデルです。そこで問題の難易度を(Wikipediaの記号で言えば)θ[i], 回答者の能力をb[i]として正解または不正解の2値の確率がロジスティック分布するというモデルになります。(ただこれだけだと若干扱いにくいので、識別率等のパラメータも入っていますが、詳細は略)
さて、モデル化できたとは言えパラメータがO(問題の数+回答者の数)だけあるものですので、解析的に計算することが困難です。TOEICはどうやってるのか知りませんが、例えばStan等でパラメタ推定するという方法がお手軽です。なんとRstanでは公式にExampleとしてIRTのモデルが配布されており、これを使うだけで簡単にIRTのパラメタが推定できます。
ただこのモデルはIndexがjjやkkになっているなど、若干扱いにくいモデルな気もするので、私は下記のように書き換えました。
data {
int<lower=1> J; // numbrt of students
int<lower=1> K; // number of questions
int<lower=0, upper=1> y[J, K]; // correctness
}parameters {
real delta;
real alpha[J];
real beta[K];
real log_gamma[K];
real<lower=0> sigma_alpha;
real<lower=0> sigma_beta;
real<lower=0> sigma_gamma;
}model {
alpha ~ normal(0, sigma_alpha);
beta ~ normal(0, sigma_beta);
log_gamma ~ normal(0, sigma_gamma);
delta ~ normal(.75,1);for (j in 1:J) {
for (k in 1:K) {
y[j, k] ~ bernoulli_logit(exp(log_gamma[k]) * (alpha[j] - beta[k] + delta));
}
}
}
あとは正解1、不正解0のmatrix dataを作成し、突っ込んで見るだけでIRTが計算できます。すごいですね。
mean se_mean sd 2.5% 25% 50% 75% 97.5% n_eff Rhat
delta 0.77 0.13 1.02 -1.56 0.10 0.78 1.51 2.59 63 1.03
alpha[1] -87.02 32.98 301.56 -279.73 -124.91 -62.00 -27.32 420.90 84 1.02
alpha[2] -80.98 36.83 361.77 -351.74 -114.98 -62.63 -30.84 471.05 96 1.01
alpha[3] 158.82 51.26 418.68 -267.69 61.02 100.14 173.25 804.92 67 1.03
alpha[4] -19.90 66.68 462.98 -716.13 11.47 36.05 64.54 305.10 48 1.07
alpha[5] 67.11 105.82 410.92 -797.50 38.92 97.84 191.13 416.25 15 1.17
alpha[6] 21.77 41.08 192.35 -89.26 -32.97 -9.99 9.61 597.90 22 1.16
alpha[7] -48.15 47.62 300.77 -527.20 -35.31 -12.04 8.99 141.71 40 1.07
alpha[8] 212.27 100.64 668.94 -172.63 56.55 112.28 180.84 1601.09 44 1.07
alpha[9] -56.79 49.54 332.28 -831.35 -41.41 -12.59 6.93 150.69 45 1.07
alpha[10] -170.93 43.87 373.47 -574.44 -212.10 -124.33 -69.93 198.09 72 1.03
beta[1] -29.03 13.71 184.55 -207.26 -65.95 -36.52 -9.09 258.44 181 1.02
beta[2] -97.16 17.89 231.61 -529.99 -127.07 -83.46 -38.86 167.99 168 1.02
beta[3] 80.57 23.90 229.00 -92.39 24.41 53.18 84.58 500.60 92 1.05
beta[4] 39.48 72.63 283.84 -846.13 -7.68 34.73 131.06 519.27 15 1.17
beta[5] -10.98 38.04 314.10 -865.74 0.98 13.90 47.77 228.96 68 1.05
beta[6] -8.32 13.52 309.31 -338.01 -79.71 -17.03 25.00 459.28 523 1.01
beta[7] -2.44 26.96 282.07 -365.96 -79.18 -27.74 45.35 470.06 109 1.03
log_gamma[1] -27.75 36.10 123.63 -398.36 -2.95 0.47 6.00 23.18 12 1.39
log_gamma[2] -24.08 32.27 116.86 -418.57 -5.61 0.50 11.56 34.16 13 1.39
log_gamma[3] -28.17 42.85 156.55 -501.14 -1.58 3.66 12.22 81.95 13 1.38
log_gamma[4] -62.23 52.16 178.41 -627.40 -37.70 -19.96 -6.41 -2.47 12 1.34
log_gamma[5] -19.78 35.04 117.68 -417.28 -0.93 5.79 17.76 38.68 11 1.46
log_gamma[6] -52.48 41.10 143.12 -461.24 -28.32 -15.49 -8.27 -4.44 12 1.36
log_gamma[7] -52.80 40.43 166.72 -525.88 -24.72 -14.55 -7.90 -3.69 17 1.27
sigma_alpha 215.69 110.14 448.73 23.63 64.75 127.21 186.27 1211.27 17 1.23
sigma_beta 176.98 76.93 318.87 14.71 54.82 93.90 165.96 1139.51 17 1.27
sigma_gamma 72.53 57.55 180.64 4.34 11.96 19.92 34.37 677.08 10 1.57
lp__ -127.04 8.90 24.62 -200.26 -130.20 -121.82 -115.55 -88.48 8 2.44
このalpha[n]ってのが各人の能力値です。特にmean(平均値)の値。
これを使ってテストの点数が問題の難易度込みで(事前に難易度を決めなかったにも関わらず)決定できます。
SRM712さぼった
TODOリスト代わりのメモ。Easyのみあとでやる。
