hotpepsiの練習帳

SRM(Single Round Match)とはTopcoder Home | Topcoderが開催する約90分(コーディング75分、休憩+チャレンジ15分)のプログラミングコンテストです。コンテスト結果はXML形式のデータフィードで取得することができ、おそらくそのデータを使ったotinn.comという素晴らしいサイトが存在していました。SRM中毒患者top100など様々なランキングを見ることができたのですが、悲しいことに去年運営をやめてしまったみたいです。

topcoderの公式サイトでは物足りないので、自分で作ってみることにしました。今回はこのサイト competitiveprogramming.info について書きます。

(以下箇条書きスタイル)

ドメイン名

競技プログラミングのサイトということで(competitiveprogramming.comは取れなかったので)competitiveprogramming.infoにした。

長いが、手で入力することはあまりなさそうなのでいいかと思ったのと、補完された場合にわかりやすいような気もする。

あとこれのおかげで競技プログラミングの英語のスペルを間違えなくなった。

サーバ構成など

この辺は手持ちの知識で適当に選んだ。

お名前.comのVPS
CentOS 6.7
nginx + Unicorn
Ruby 2.16
Rails 4.0
Knockout.js

SSLについて

OAuth認証でHTTPだと片手落ちなので、RapidSSLで証明書を取り、HTTPはlistenせずHTTPSのみにした。

せっかくなのでQualysのSSL Server TestでA+になるように設定した。そのためおそらくAndroid 2.3やIE6ではつながらない。

SRMのデータフィードについて

SRMについて、以下のXMLフィードがある。

Coder List
Active Algorithm Coder List
Algorithm Round List
Algorithm Round Results
Algorithm Rating History
Algorithm Practice Rooms
Algorithm Practice Room Details

competitiveprogramming.infoの実態

SRMの一覧 https://competitiveprogramming.info/topcoder/srm

コンテストのタイトルの欄は、公式のMatch Overviewに飛ぶ。Division 1/2のリンクはそれぞれの結果に飛ぶ。

Algorithm Round Listから取得。コンテスト終了後に手作業で更新している。

内部ではroundというモデルに記録。

div1,div2それぞれのSRMの結果 https://competitiveprogramming.info/topcoder/srm/round/16624/div/1

otinn.comと同様、スコアから(公式の)コンテストの提出結果に飛べる。

タイトルから公式のMatch Overviewに飛べる。問題文にも飛べる。タブをクリックするとソートできる。

Algorithm Round Resultsから取得。コンテスト終了後に手作業で更新している。

内部では部屋情報をroom、履歴をhistoryというモデルに記録。ソートにはjquery-tablesorterを使用。

各個人の参加記録 https://competitiveprogramming.info/topcoder/srm/history/hotpepsi

個人ごとのhistoryを表示する。実は一人だけ表示が特別。

twitter login https://competitiveprogramming.info/topcoder/handle/hotpepsi

OAuthでログインできる。topcoder IDとtwitter IDをひもづけられる。

Practice room statusのため。

Practice room status https://competitiveprogramming.info/topcoder/srm/practice/hotpepsi

practice room(コンテスト終了後に解放される練習部屋)の提出状況を確認できる。

ログインしてtopcoder idとtwitter idをひもづけておくと自分のpractice room statusのページが作成される。arenaで提出してから、practice room statusの右の欄をクリックすると、サーバ側でデータを取りに行って、その部屋の提出状況が更新される。

なぜこういう作りになっているのかというと、arena上で提出してもtopcoder側が教えてくれるわけではなく、自分で取りに行くしかない。しかし部屋はたくさんあり、ポーリング(=ひたすら取りに行くこと)もしたくない。arena上では誰でも提出可能だが、全員の分を記録するのはさほど意味がないし、更新も遅くなる。そんなわけで、登録制＆手動更新にした。

内部ではpractice_roomとpractice_historyというモデルに記録。

div1/div2で別の部屋(別のID)なのだが、まとめたほうが見やすいので同じ行に表示している。

ここではAjaxとKnockout.jsを使って行単位に書き換えている。

Top 100 worst SRM addicts https://competitiveprogramming.info/topcoder/srm/addicts

SRM中毒患者の一覧。ほぼ自分用の機能。(ランキング内で現在も継続中なのは自分を含め5人)

historyから生成。コンテスト終了後に手作業で更新している。

addictというモデルに記録。

工夫したところ

ソートできる

今までの最高順位とかがすぐわかる。

更新中にぐるぐるする

turbolinksを使っておりページ間の遷移が(全体のリロードではなく)ajaxになっていて、遷移中もbodyを表示することができるので、glyphiconのアイコンを表示するようにしてみた。はじめてturbolinksをうまく使えた気がする。

困ったことなど

problem id

問題文のIDはAlgorithm Round Listではわからないので、Algorithm Round Resultsのデータから、roundにひもづけている。Problem archiveのHTMLをパースすればわかるが、これ相当のXMLのフィードを用意して欲しいところ。

contest id <-> practice id

Algorithm Round Listのround idとAlgorithm Practice Roomsのround idは異なり、それを関連付けるデータが存在しないので、同じ名前のroundを適当にひもづけている。

コンテストがunratedだとroundが存在しなかったりして、その場合は手作業で作ったり、同じ問題が使われているコンテスト(College Tour SRMとか)で誤認するバグが出たりした。

新規登録者

最近のAlgorithm Round Resultsには新規登録者が含まれていない模様。topcoderに報告済だがまだ返事なし。

coder list

どうやらCoder ListとActive Algorithm Coder Listを足しても全員ではなさそうな感じ。国別のランキングを作るのに困る。

公式サイトデザインリニューアル問題

公式サイトが11月のリニューアルで普通のcompetition historyが見られなくなってしまった。そのおかげ(?)でりんごさんに紹介してもらったりした。

最近運営が雑に感じるので来年は巻き返してほしい。

今後の展望

otinn.comにあった色々な機能がまだまだ全然できていないので、ゆっくり実装していく。二つのIDの対決結果の表示とか。

問題の作成者やタグ(貪欲とかDPとか)を取得する。これはフィードがないのでクロールで。

topcoder&AtCoder meetupのときに発表したのですが、使ってくださった方々、宣伝してくださった方々、ありがとうございます。細く長く続けていく予定なので、今後ともよろしくお願いします。

明日はyuizumi_y5iさんです。

SRM 675もあります!

コメントを書く

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20151208

2015-11-15

SRM 654

DP | 22:27

https://competitiveprogramming.info/topcoder/srm/round/16318/div/1

https://competitiveprogramming.info/topcoder/srm/round/16318/div/2

Div1 Easy (250) SquareScores

問題

アルファベットと?からなる文字列Sがある
?がどの文字になるかの確率が与えられる
Sから連続した文字を取り出したものを部分文字列とする
全て同じ文字からなる部分文字列の総数をスコアとする
スコアの期待値を求める

方針

DP
文字a-zについてそれぞれ計算する
1文字のときの計算は、位置iがcならスコア1.0、?ならスコアp[c]
n文字はn-1文字からDPで計算できる
Passed System Test
https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_654/SquareScores.cpp

結果

o-- 138.33pts 134th/350 rating 1454 -> 1504

今年初黄色。DP必要ないっぽい。

http://togetter.com/li/799762

コメントを書く

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20151115

2015-07-28

SRM 653

23:55

https://competitiveprogramming.info/topcoder/srm/round/16317/div/1

https://competitiveprogramming.info/topcoder/srm/round/16317/div/2

Div1 Easy (250) CountryGroupHard

問題

人々が一列に座っている
同郷の人が連続して座る
同郷の人の人数を聞いた結果の配列aが与えられる
a[i]がゼロなら質問しておらず、正なら人数が入っている
残りの人に質問しなくても、構成が一意かどうかを求める

方針

メモ化再帰
[pos,N)の区間が一意かどうかを返す
Failed System Test
ゼロの扱いがバグっていた
(解き直し)
[pos,N)の区間が何通り(以上)かを返す。不可能であればゼロを返す。2通り以上あれば2を返す
区間内でゼロでない最初の要素を見つける。全部ゼロなら、ゼロの個数を返して終了
その位置と値でありうるパターンを列挙する(たとえば3の場合、末尾で3のとき、真ん中のとき、先頭のとき)
数字が矛盾しない(333や300など)なら、左右の矛盾をチェック
左側の判定は左側のゼロが1個以下かどうか
右側の判定は再帰
[0,N)が1かどうかが答え
https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_653/CountryGroupHard.cpp