Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

2016-12-01

[] AtCoderの昔の問題を難易度推定する 00:09 はてなブックマーク -  AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calender 2016 1日目の記事です。


先日、Twitterでこのような発言を見かけました。

AtCoderの過去問が今の基準だと何点になるのか知りたい

https://twitter.com/hogeover30/status/785894012716654593

やってみました。


一応、背景を書いておきます。

以前のAtCoder Regular Contest(以下ARC)・AtCoder Beginner Contest(以下ABC)では、基本的にそれぞれの問題は100点満点でした。

2016年7月にAtCoderがリニューアルされた際、難しい問題は高い点数となるよう、難易度に応じた配点がされるように変わりました。

そこで、以前の問題が最近の基準では何点くらいになるのかを、ユーザーの回答状況を元に推定しました。


AtCoderリニューアル後のコンテストの問題に対する、各ユーザーの正解/不正解の結果と配点を教師データとして機械学習し、過去の問題に対する正解/不正解の結果をテストデータとしています。


結果はこちらにあります。

https://tomerun.github.io/atcoder_statistics/estimated_scores.html


  • どうしても古いコンテストほどデータが少なくて推定しづらい様子。ABCのA問題が250点くらいといった高すぎる数値が出ている
    • 逆に、新しめのものはそこそこよさげに見える
    • こういった状況は他の機械学習案件でもありそうなんだけれど、うまく扱う方法あるんだろうか
  • ABCのD問題にもけっこう難しいのが紛れている
    • あまり出てないので知らなかった
  • 難易度順が逆転してしまっているところはあんまりない
  • これくらいの推定なら正解者数や正解率だけの分析でも出せるんではないかという気もしますが…
  • 解ける人が数人しかいない最高難易度帯の問題は、そのコンテストに誰が参加していたかによって結果がかなり影響されてしまうので、信頼性低そう
    • おおまかには、強い人がコンテストに出ていて解けなかった場合に推定スコアが高くなるという仕組みなので、あまり強い人が出ていなかった場合、推定スコアが高くなりようがない


実装に関しては、だいたいはscikit-learnのSVMに放り込んだだけですが、細々とした話としては次のようなことがあります。

  • 全ユーザー使ってしまうとデータがすごくスパースになって精度下がってしまうので、過去のコンテストに100問以上参加しているユーザーのみを計算に使いました
    • 対象ユーザーは236人でした
  • 過去に一部、満点が101点という問題がありましたが、100点以上を正解として扱っています
  • 「後ろのほうの問題だけ解いて他は無視」という参加をする人もいるので、コンテストの後半の問題は提出しているのに前半の問題は未提出の場合、前半の問題は不正解ではなく不参加という扱いにしています
    • 逆に前半だけ提出していて後半は未提出の場合、後半の問題は手が出なかったとみなして不正解扱い


せっかく今回いろいろデータを集めてきたので、他にもなにか面白い分析をやりたいですね。アイディアがある人はぜひ教えてください。


Advent Calendar2日目は、tubo28さんの「未定」と、snuke_さんの「IOIへの出題について」です。お楽しみに!

2015-12-01

[]すごいサブミット 00:42 はてなブックマーク - すごいサブミット - TopCoderの学習のお時間


これは Competitive Programming (その2) Advent Calendar 2015の1日目の記事です。


Advent Calendarの基本に返って、すぐ書ける記事にします。

これまでにコンテストで見た、印象に残ったサブミットを列挙します。

他人のコードを勝手に紹介することをお許しください。


SRM436

https://community.topcoder.com/stat?c=problem_solution&rm=300564&rd=13698&pm=10336&cr=10597114


想定解がFFTの問題だったのですが、インラインアセンブラで気合いで通しています。

1発ACを要求されるSRMで、36分でこのコードを書いて通すのは、当時の界隈にかなりの衝撃をもたらしました。


2010 TCO Marathon Round 2

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10989&rd=14273&cr=22696357&subnum=8


このマラソンマッチは完全なる高速化ゲーでした。

というわけでJITです。


Marathon Match 78

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=12444&rd=15570&cr=21688563&subnum=13 (重いので注意)


圧勝した人のコードです。

皆が焼きなます中、Pythonで遷移パターンを列挙して埋め込んでDPしたみたいです。


NSA Marathon Match Event 1

https://community.topcoder.com/longcontest/?module=ViewProblemSolution&pm=10676&rd=14176&cr=7462740&subnum=3


これはコードよりも 順位表 を見てもらった方が良くて、訳が分からない点差が付いています。

これは暗号解読の問題だったのですが、どうも一人だけまともに解読できたらしいです。

コードで何をやっているか読めた方は来年のAdvent Calendarのネタにでもすると良いのではないでしょうか。ぜひしてください。


AtCoder Regular Contest #030

http://arc030.contest.atcoder.jp/submissions/286413


コードを見ても何をやっているのか分からないと思いますが、見るべきは提出時間で、コンテスト開始3秒後にサブミットされてACを取っています。

サンプルから解答を推測するプログラム、なのでしょうか??


お誕生日コンテスト

http://birthday0410.contest.atcoder.jp/submissions/128080

http://birthday0410.contest.atcoder.jp/submissions/127943


これも順位表を見てもらった方が良くて、WA回数が大変なことになっています。

問題の性質的に、インプット解析でがんばれてしまったのですね…。


なおこのようなひどい(褒め言葉)問題であるにもかかわらず、まともな方法で満点を得ているサブミットもあってこちらもすごい

http://birthday0410.contest.atcoder.jp/submissions/127561


おわりに

ほかにも興味深いコードがあったら教えてください!!

2014-12-01

[][] MarathonMatchトレーニングのための過去問レビュー 01:01 はてなブックマーク -  MarathonMatchトレーニングのための過去問レビュー - TopCoderの学習のお時間


これは Competitive Programming Advent Calendar 2014 1日目の記事です。


MarathonMatchで成績を上げていくには、他のスポーツと同じく実践が不可欠だと思います。

しかし、最近は通常の(=TCO予選みたいな組み合わせ最適化を問う)MarathonMatchの開催回数が少ないのでなかなかその機会が得られません。

信じられないかもしれませんが、2008年ごろは月1回以上のペースでMarathonMatchが開催されていたんです…。


ならば過去の問題ストックを使って自主練するしかない!

ということで、過去に自分が参加したMarathonMatchについて、問題をジャンルわけしてコメントを付け、オススメ度を☆で表しています。

ジャンルわけは便宜上という側面が大きく、この方針ではないとダメ! というわけではないです。

あと、ネタバレありなので要注意。


リンク先はPracticeの問題文です。

Practiceが存在しないものがいくつかあって、それらにはリンクを張っていません。

なお、Practiceにないものも含めて過去のMarathonMatchの一覧を見るには、Match Winners のページがよさそうです。


焼きなまし


ざっくりいえば焼きなましをするんだけど、もちろん焼きなましただけではだめで、その適用形態は多彩です。

  • TCO14 Round3 CollageMaker [☆☆☆]
    • そもそも、焼きなまし(というか、逐次的改善)可能な形にできたかどうかが上位との分かれ目といった感じでした
    • 解の探索以外でちょっと面倒な要素が多いので、練習するなら他の問題の方が良いかなぁ
  • TCO13 Round3 CirclesSeparation [☆☆☆]
    • 良い近傍の取り方がとても難しい
    • 僕は本番でまともな方法を実装できずに撃沈しました
  • Marathon Match 78 FixTheFence [☆☆☆☆☆]
    • 良い近傍の取り方が難しい
    • 問題としてはシンプルなので練習によさそう
    • ところで本番1位の人の解法は焼きなましではなく他の人たちと全然違う方針でした。かっこいい
  • TCO10 Round2 CellularAutomaton [☆☆]
    • 完全に高速化ゲー。高速化の訓練としては良いかもしれませんが…
  • TCO10 Round1 Planarity [☆☆]
    • これもかなり高速化ゲーの印象(12時間しかやってないけど)
  • Marathon Match 56 EnclosingCircles [☆☆☆☆]
    • よくMarathonMatchの問題例として取り上げられる、理解しやすい問題
    • 本番の結果は意外とばらけていて、焼きなましの職人芸スキルで差がついた、という印象
  • Marathon Match 54 TilesPuzzle [☆☆☆]
    • 本番で自分が焼きなましでやったのでここに入れましたが、forumを見る限りは焼きなましてる人は少数派っぽい
    • いろいろなヒューリスティック探索ができそう

ビームサーチ


最近ビームサーチばかりやってる気がするけど、挙げてみたら思っていたより少なかった。

  • TCO14 Round1 SquareRemover [☆☆☆]
    • 高速化寄り
    • アルゴリズムにやらせると、人力で遊んだ場合より遙かに良い点数を出すのが面白かった(どうでもいい)
  • TCO13 Round2 FragileMirrors [☆☆☆☆]
    • 良い評価関数を作ることがもちろん大切なんだけど、もっと重要な要素がひとつあって、それを見つけられないと勝負にならない感じだった
    • 問題の性質をよく考える訓練になって良い
  • TCO12 Round1 BlackAndWhiteGame [☆☆]
    • 探索が可能な形をつくるのが全く自明ではなくて大変
    • 正のスコアを出すまでちょっと遠いので練習としてやるにはつらいかもしれない

マルチエージェント系


複数のユニットを動かして、協調して何かやらせる問題。

実装が難しくなることが多いです。

  • TCO13 Final GatheringResources [☆☆☆]
    • 実装ゲーに近かったと思う
    • とはいえ12時間しかやっていないのでもっと時間かけたときにどうなるかは未知数かな
  • Marathon Match 55 CoalMining [☆☆☆]
    • あまり印象に残っていない…。オーソドックスな問題だったと思います

パターン決め系


良い解では全体がどのような形になるかを見出すことが最重要になる問題たち。

後はそのパターンの中で細かく探索をしたりする。

他人の解をビジュアライザで見ると面白いことが多い。

  • TCO14 Round2 RectanglesAndHoles [☆☆☆]
    • パターンを想定するまではできても、それを実装するのが難しい問題だったと思います
  • Marathon Match 74 AntiTravelingSalesperson [☆☆☆☆]
    • 格子点にしか置けないという制約がある中でうまいパターンを作るには、適当にやってもダメでよーく考えないといけない
    • これも1位の人は違った方針でやっていてかっこよかった
  • TCO09 Round2 Gearing [☆☆☆☆]
    • 逐次的な改善が可能な形でパターン決めてあげないと良いスコアにはならない
    • 本番に自分が参加したときは、greedy的な方針で決めうちしてしまってイマイチな結果でした
  • Marathon Match 49 MegaParty [☆☆☆☆☆]
    • 問題の性質をよく考えて、全体の形を作る事が最重要。教育的です
    • 本番に自分が参加したときは、何も考えず単純に焼きなましただけだったのでイマイチな結果でした

不完全情報・確率評価系


初めに情報が全部は与えられないタイプの問題。結果の期待値を評価しながら次の一手を選んでいくプログラムになる。

個人的にはこの形式はけっこう好き。

  • TCO12 Final PolygonEstimation [☆☆☆]
    • 本番で方針が大きく2つに分かれて結果も拮抗していたのが面白かった
    • なかなか実装Hardです
  • TCO11 Round1 ImageScanner [☆☆☆]
    • colunさんがガチ確率評価をやって圧勝したことで有名(?)な回
    • 問題テーマとしては、情報科学的な観点でもとても面白いものではある
    • 外部のデータファイルを処理しないといけないので少し取っつきづらいかな?
  • TCO10 Final CollapsingMaze [☆☆]
    • 確率的に即0点になってしまうという大味な問題。どこまで攻めるかの調整が肝
    • Practiceではテストケース数が限られるから運ゲー要素が強くなってしまいそう
  • Marathon Match 65 CuttingFigures [☆☆☆☆☆]
    • ある手を指したときの期待値をしっかり評価することが求められる
    • ルールもシンプルだし、良い練習になりそうな問題です
  • Marathon Match 53 TilesMatching [☆☆☆☆]
    • とにかく良い評価関数を作れるか勝負
    • これもう一回やりたいのだけどなんでPracticeにないんだ…
  • TCO09 Round1 ReliefMap [☆☆☆☆]
    • 取れる選択肢の自由度が非常に高くて、次に何をするかをどうやって決めたら良いか難しい
    • 実装も大変で、Round1(当時ルール)にしておくにはもったいない良問でした

その他・ノンジャンル・総合力


  • TCO11 Round2 QualityPolygons [☆☆☆☆☆]
    • いろいろな方針が考えられて、まさに総合力といった感じ
    • がっつり練習したかったら、ここに挙げた中で一番オススメです
  • TCO10 Round3 SubgraphIsomorphism [☆☆☆☆]
    • ヒューリスティック枝刈り探索勝負。もう一度やってみたいがこれもPracticeにないの残念
  • TCO09 Round3 BounceOff [☆☆☆☆]
    • まず、ある程度まともに動作する解を作れるかどうかが難しくて、Round3(当時ルール)に進んだ人たちでもかなり苦労していた
    • この問題は特に、SRM的な発想では全く方針決められない気がします。その意味では良い例題
    • ビジュアライザが楽しいです
  • Marathon Match 48 WatermarkSequence [☆☆☆☆]
    • Marathon史上最良問との呼び声もある問題。僕が初めてMarathonに参加した回でもある
    • めちゃめちゃ面白いけどだいぶ難しいので、練習にやってみるなら覚悟して

特殊・非推奨


ちょっと特殊なところがあってあまりお勧めできない問題たち。

  • TCO11 Round3 StringCompression [☆]
    • あまり最適化という感じではなくてつらかった
  • NSA Marathon Event 3 BrokenClayTile [☆]
    • テストケース生成リバースエンジニアリングゲーでつらかった
  • Marathon Match 66 DigitsPattern [☆]
    • 最良解を出せてしまう人大量発生でつらかった
  • Marathon Match 58 IsolatedPrimes [☆]
    • 数学ゲーかつ埋め込みのためのローカル計算でつらかった

やったことないやつら


問題文を読んだだけでコードを書いたことがない回もたくさん残っていました。それらの中で面白そうなのを列挙します。

自分が練習会をするとしたら、この中から選ぶことになります。

(この記事の公開と同時に練習会を始めようかとも思っていましたが、CodeVSKaggleが出てきたのでまたいずれ)

2013-12-24

[] 国別レーティングヒストリー 01:03 はてなブックマーク -  国別レーティングヒストリー - TopCoderの学習のお時間

これは Competitive Programming Advent Calendar 2013 25日目の記事です。


TopCoder Algorithm部門の国別レーティングについて、これまでの推移が気になったのでデータフィードから計算してグラフにしてみました。

http://tomerun.info/article/tc_ratings/index.html


眺めてみると次のようなことがわかります。

  • 日本での流行り具合は、2007-2008年に一度波が来て、少し間を置いて2010年-2011年にまた伸びてます
    • 前者はITMedia記事効果?
    • 後者は最強最速アルゴリズマー講座と蟻本効果?
  • りんごさんの引退は2012年4月頃に効いてきてるはずだけど、そこまで変化ないですね。ユーザーが数百人いたら、1人ぐらいではあまり影響しないのか
  • 最近レーティングが伸びてきてるのは、台湾とカザフスタンです。今後に注目
  • 2008年に中国のアクティブユーザー数が爆発しているのは中国専用イベントがあったからだと思われます
  • 近年では、4月〜6月にアクティブユーザー数が増えて年末に向けて減っていく傾向が見られます。TCO効果だろうか
  • 2012年12月に全体的に一度レーティングががくっと下がってるけど理由がわからない。集計ミスかなあ
  • ここ2年くらいは全体的にユーザー数が頭打ちなのが見て取れます
    • 中の人ならずとも今後の行方が気になります…
    • CodeforcesやCodeChefが出てきたのも影響?

と過去を振り返りつつ未来を思いつつ、2014年も good luck & have fun!

2012-12-21

[]Kaggle - making data science a sport - 00:26 はてなブックマーク - Kaggle - making data science a sport - - TopCoderの学習のお時間


これは Competitive Programming Advent Calendar Div2012 21日目の記事です。

機械学習・データマイニングのコンテストを開催しているKaggleについて紹介します。


概要


Kaggleは、あちこちの企業・団体とコラボして、実世界のデータに基づいた機械学習・データマイニング系のコンテストを開催しています。

TopCoderのMarathonMatchでもここ1,2年くらいそのようなコンテストが増えていますが、それを専門に行っているクラウドソーシングプラットフォーマーがKaggleです。

(MarathoMatchについては、Machine Learning Advent Calendarでのnico_shindanninさんの記事で紹介されているのでそちらも参考にしてください)


過去のものも含めたコンテストの一覧です。

http://www.kaggle.com/competitions

TopCoderのこの手のコンテストではだいたい賞金総額1万ドルですが、10万ドルとかもっと賞金額が高いものもたまにあります。


特徴


TopCoder Marathonと比べて異なる点を中心に、Kaggleのコンテストの特徴を挙げていきます。


実行環境・解答の提出

プログラムを提出するのではなく、訓練データとテストデータ(主にはCSV)をダウンロードしておき、テストデータに対してローカルで何か処理して得た予測結果を提出します。

提出するフォーマットもCSVの場合が多いようです。

なので、言語やツールは何でも好きなものを使えます。


ただし、上位に入って賞金をもらうためには、使用したコードをOSS(具体的なライセンスはコンテストごとに指定される)として公開する必要があります。

また、コードだけではなく、使用した手法を解説したドキュメントも必須です。

コンテストの結果ページ(例:http://www.kaggle.com/c/asap-sas/details/preliminary-winners)でそれらのリソースが公開されているので、上位者のやったことを読んで学習に使えます。


順位表には、コンテスト開催中はテストデータの1/4くらいについての結果が表示されています(Public Leaderboard)。

コンテスト期間が終了すると、残りの3/4くらいの結果を元に最終順位が決まります(Private Leaderboard、システムテストに相当)。

f:id:tomerun:20121220225549p:image

(なんか画像をオリジナルサイズで表示できないので詳しく見たい方はクリックして開いてください)


過学習のせいで激しく順位が入れ替わることもしばしばあるみたいです。

例えば、つい先週まで開催されていたダークマターを探せという怪しげなコンテストでは、

事前順位表で20位だった人が最終的には1位になっており、逆に事前順位表で2位だった人が39位まで落ちています。


提出回数には、"1日2回以内"などのように制限があります。


協力

大体のコンテストでは、数人でチームを組んで参加できます。途中でチームを合併することも(人数制限が許せば)可能なことが多いみたいです。


また、Kaggle内のフォーラムで、問題の内容について公開で議論することも歓迎されています。

スポンサーにとっては最終的にコンテストから得られる結果が良いものになったほうがうれしいわけですからね。

これはTopCoderでは厳しく制限されているのと対照的です。


コンテストの種類

誰でも参加できて、最も高いスコアを出した人が優勝で賞金をもらう、というのが普通のタイプのコンテストですが、それ以外の種類もあります。

  • Getting Started Competitions
    • 練習のためのコンテストです。賞金無しで、他のコンテストよりも長い期間(1年くらい)開催されています。
    • 2012年12月現在は、手書き文字認識(MNISTデータセット)の問題と、タイタニックの乗客データから生存者かどうかを識別する問題の2つがあります。
  • Recruiting Competition
    • 企業が人を雇うために開催しているコンテストです(なんとあからさまな)。
    • もちろんこれに勝ったからといって無条件で雇われるわけではないみたいですが…
    • チーム参加は不可です。
  • Visualization Competition
  • Masters Competition
    • 過去のコンテストで良い結果を出している人だけが招待されるプライベートなコンテスト、らしいです。

ベンチマーク

主催者が用意した、シンプルな手法によるプログラムとその結果が、ベンチマークとして提供されています

たとえば"全部ランダム"とか"てきとーにRandomForestに入れてみた"とか"てきとーにk-NNしてみた"みたいな。

まずはこのスコアを超えることが目標になります。

自分でいろいろ考えた要素をモデルに含めるよう頑張って実装しても、単純なベンチマーク解答に負けたりするので面白い。


コンテストの流れ


"Getting Started Competitions"として開催されている、タイタニックの乗客データ分析の問題に参加している様子を見ていきます。


テストデータの入手

テストデータは次の場所にあります。

http://www.kaggle.com/c/titanic-gettingStarted/data

f:id:tomerun:20121220233456p:image

表が5行ありますが、一番上が訓練データ、一番下がテストデータ、真ん中3つがベンチマークのプログラム/解答です。


一緒に、データのフォーマットが書かれています。

タイタニックの各乗客について、年齢や性別、何人の家族と一緒に乗っていたか、チケットの値段はいくらか、乗船した港はどこか、などのデータが並んでいます。

これらのデータを元に、それぞれの乗客が事故の生存者だったかどうかを判別する問題です。


データ分析・実装

とりあえず表計算ソフトで開いて訓練データを眺めてみます。

てきとーに統計を取ってみると、性別が生存者だったかどうかにとても大きく関連していたり、名前のようにほとんど関係なさそうなデータが含まれていたりすることがわかります。

また、現実世界のデータには良くあることですが一部のフィールドで値が抜けているところもあるので、どうにかして扱ってやらないといけません。

これについては練習コンテストということもあり、ベンチマークプログラムについて説明したチュートリアルの中にも書いてあります(How do I clean and fill? のところ)。


今回は、乗客の名前みたいに明らかに結果に関係なさそうなデータを除いて、残り全部の要素を使ってナイーブベイズを組んでみました。

年齢やチケット額みたいに値が連続値に近い要素については、適当に離散化しています。

また、過学習を防ぐため訓練データを使って5-fold cross validationしてパラメタを決めました。


提出

テストデータに対してプログラムを実行し、得られた結果をCSVで提出します。

f:id:tomerun:20121221001927p:image

提出するときに、一緒にコメントを付けられます。

コンテスト終了時に、どの提出を最終的なものとして使うかを自分で選ぶ(選ばなかったら自動的に最新のものになる)のですが、そのときにコメントが参考にできます。


結果を提出すると、スコアが計算されて順位表に反映されます。

f:id:tomerun:20121221000941p:image

以前RandomForestを試したときに自己ベストのスコアを出しており、今回のスコアはそれを超えることはできなかったようです。


自分の過去の提出はこんな感じで一覧できます。

f:id:tomerun:20121221000956p:image


順位表の見た目が正直いまいちですが、現在これを改善するためのVisualization Competitionが開催されているので期待しましょう。


感想など

  • 提出すると、訓練データのクロスバリデーションで出ているスコアよりもかなり小さいスコアしか取れず、汎化性能の高いモデルを作ることの難しさを感じています
  • 参加者の平均レベルはかなり高そう。wikiにまとめられたリソースを参考にし、上位者のドキュメントをしっかり読んでいったらこのKaggle内だけで機械学習系の学習が完結してしまいそう
  • コンテスト期間が1ヶ月〜2ヶ月くらいのものが多いので、突然コンテストが始まってもスケジュールを調整しやすい。この点TopCoder MMは辛い
  • TopCoderのforumに「TopCoder vs Kaggle」というトピックが立っています。TopCoderMarathonが機械学習・データマイニング系のコンテストを今後も継続するとしたら、生き残るのはどっちでしょうね…
    • 今のところ、コンテストの参加者数・賞金額・開催数いずれもKaggleのほうが少し多いくらいです