AtCoder Problems を支える技術
はじめに
AtCoder Problems というサービスを作っています。最近作り直しています。
http://beta.kenkoooo.com/atcoder/
これは AtCoder の提出を全部クロールして、一覧で見れるようにしたものです。最近は機能が増えすぎていますが・・・
ソースコードも公開しています。このプログラムの中でどんなことをしているのかを書いていきたいと思います。競技プログラミングはそんなに関係ないです。
スクレイパー
Scala で書いています。ScalaScraper でクロールもスクレイピングもやってくれるので、それに任せています。
やっていることは以下のとおりです。
- コンテスト一覧をクロールして DB に入れる。
- DB のコンテストを順番に見ていき、そのコンテストの問題をクロールして DB に入れる。
- コンテストを順番に見ていき、そのコンテストの提出をクロールして DB に入れる。全てクロールすると多すぎるので、既に DB に入っている提出が出るまで最新の方から見てクロールする。
- クロール漏れするかもしれないので 1 日に 4 回だけ全ての提出をクロールする。
集計
ユーザーが問題を解いた数や、各問題の正解者数、実行速度最速の提出やコード長が最短の提出などを集計しています。これらの値は API でリクエストが来ますが、来るたびに計算していると遅いので予め計算しておきます。やっていることは SQL クエリを投げるだけです。ユーザーの提出をできるだけ早めに反映するため 5 分ごとくらいで実行しています。
API サーバー
フロントエンドからは JSON で出力を返す API を叩いています。API サーバーも Scala で書かれていて、サーバーは Akka HTTP で、SQL 部分は ScalikeJDBC を使って書いています。
可能ならレスポンスを gzip で返したり、ETag を見て変更がなければ 304 を返してキャッシュを使ってもらったりなどの工夫がありますが、このへんは Akka HTTP がよしなにやってくれています。
フロントエンド
フロントエンドは TypeScript と React で書いています。JS 業界は gulp だの bower だの browserify だの webpack だの mocha だの chai だの無限にインストールしなければならないイメージでしたが、TypeScript のチュートリアルどおりにやったところ、トランスパイルは webpack 、テストは jest だけで十分でした。
TypeScript は VSCode でプラグイン無しで快適に書けるのでとても良いです。素の JavaScript を書くことは一生ないでしょう。
得点の予測
AtCoder の rated のコンテストでは各問題に得点が設定されていますが、そうでない問題は rated の問題と違う基準で得点が設定されているので、推定してみることにしました。
AtCoder で 300 問以上解いているユーザーをヘビーユーザーとして、ヘビーユーザーの各問題についての「解けた」「提出したが不正解だった」「提出していない」を特徴量にして、思考停止 XGBoost で predict しました。
AtCoder で問題を解くと、ヘビーユーザーとして特徴量作成に使われたり、各問題の特徴が正確になったりして、反映される予測値も正確になっていくはずなので、みなさん問題を解きましょう。
まとめ
Scala はいい。TypeScript もまあいい。
