Introduction To TopCoder, 今日からはじめるTopCoder
最近自分のまわりでtopcoderに興味をもつ人が多いので、入門記事を書いてみます。
TopCoderとは
TopCoderとはオンラインで開催される、プログラミングコンテストです。誰でも無料で参加でき、世界中の参加者たちと腕を競い合えます。また、後述するICPCやGoogle Code Jamのような年に一回開催される大会とは異なり、月に数回開催されるので、コンスタントに参加できます。個人で参加でき、予選などもなくいつでも参加できるので、プログラミングやアルゴリズムの練習・学習に最適だと思います。
世界中の人が参加するので、登録や問題文は全て英語で書かれています。プログラミングをしながら英語も勉強できるなんて最高ですね！
SRMの流れ
TopCoderのコンテストはコーディングのコンテストだけではなく、設計やデバッグ、高校生専用大会など、色々な種類があり、日々活発に競技が行われています。その中でも最も参加人数の多いアルゴリズムのコンテストがSRM(Single Round Match)です。
SRMではEasy, Medium, Hardという得点の違う3問が出題されます。制限時間は75分間で、その間に解答します。それぞれ、問題文とインプット/アウトプットの要件と例が示されるので、それに沿ったメソッドを書いて提出します。言語はJava, C++, C#, VBの中から一つを選択します。75分という制限時間からもわかる通り、コードの行数はそれほど長くはならず、100行いくとけっこう長いなあと感じるくらいです。それよりもアルゴリズムを考えさせたり、数学的なひらめきを要求する問題が多いです。またコードは2秒以内に実行できなくては行けないので、実行時間にも気をつける必要があります。
参加者にはratingが付与され、ランク付けされます。コンテスト各回の結果に応じて変動します。ratingの計算方法はこちら。参加者はratingのスコアごとに色分けされます。
- red: 2200+
- yellow: 1500-2199
- blue: 1200-1499
- green: 900-1199
- gray: 0-899
- white: not rated (コンテスト未参加)
red coderは全世界で220人ほどしかいない、めちゃくちゃすごい人達です。会員登録数が約22万人なので、この数値で計算すると上位0.1%ということになります。さらにその中でも特に優秀なプレイヤーには、白丸がついたアイコンが表示されます。また、red coderになることは、単にコミュニティの羨望を集めるだけではなく、海外では就職にも有利になるそうです。
TopCoder Statistics - Top Ranked Algorithm Competitors
またSRMはdiv1とdiv2の二つのグループに分かれています。div1にはブルー以上のratingの人しか参加できず、また問題もdiv1の方が難しくなっています。
このようなコンテストが月にだいたい2, 3回開催されています。
例題
例として、こんな問題が出ます。
Problem Statement Computers tend to store dates and times as single numbers which represent the number of seconds or milliseconds since a particular date. Your task in this problem is to write a method whatTime, which takes an int, seconds, representing the number of seconds since midnight on some day, and returns a string formatted as ": : ". Here,represents the number of complete hours since midnight, represents the number of complete minutes since the last complete hour ended, and represents the number of seconds since the last complete minute ended. Each of, , and should be an integer, with no extra leading 0's. Thus, if seconds is 0, you should return "0:0:0", while if seconds is 3661, you should return "1:1:1".
要約すると、秒換算の時間が与えられるので、それをHH:MM:SSというフォーマットで返せ、という問題です。これはdiv2 easyという簡単な問題ですが、これならとっつきやすそうですよね。
登録
では、早速登録してみましょう。
Programming Contests, Software Development, and Employment Services at TopCoder
このページの右上、"Register Now"から行います。けっこう項目が多くて面倒ですががんばります。
練習してみる
登録が終わったら、早速練習してみましょう。practice room という練習専門の部屋があり、ここでは過去のコンテストの問題を全部見ることができます。practice roomでの問題はratingに反映されず、何度でもサブミットやシステムテストをすることができるので、思う存分練習できます。まずはdiv2のeasyからやってみるのがいいでしょう。方法についてはこちらのサイトに詳しいです。
雑記/TopCoderに挑戦 - nodchip’s web site
補足点としては、summery という緑色のボタンを押すと、他の人のコードを見ることができます。非常に勉強になるので、解いた後は他の人のコードも見るといいと思います。
Pluginの設定
コンテストを戦うにあたって、プラグインの設定は必須です。プラグインを導入することに依って、ローカルでコーディングとテストができるようになります。公式のアプレットではなく、使い慣れたエディタとシェルを使用できるので、スピードが飛躍的にあがります。
プラグインの設定はgulfweedさんの記事が素晴らしいです。
TopCoderでCodeProcessor+TZTester+FileEdit - Gulfweed
参考までに、僕のC++のテンプレートはこれです。
$BEGINCUT$ $ENDCUT$ #include#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class $CLASSNAME$ { public: $RC$ $METHODNAME$($METHODPARMS$) { } $TESTCODE$ }; // BEGIN CUT HERE int main() { $CLASSNAME$ ___test; ___test.run_test(-1); } // END CUT HERE
プラグインを導入し、問題をアリーナ上で開くと、ローカルに "methodName.cpp" というファイルが作られます。このファイルの中にクラスの宣言やテストコードなど（設定次第では問題文も）が全て含まれています。このファイルにコードを書き、できたら普通にコンパイル/実行するとテストが走ります。コンパイルは、topcoderサーバで-O2オプションがつけられるそうなので、実行時間がシビアな問題もあるので、ローカルでも同様のオプションをつけることをお勧めします。僕はいつもこんな風にしています。
% g++ -Wall -O2 foo.cpp && ./a.out
テストが大丈夫そうなら、サブミットします。ローカルのファイルの内容はアリーナにも反映されているので、あとはアリーナ上でコンパイルし、サブミットするだけです。
本番への挑戦。予定の確認
練習の成果を本番で発揮しましょう。SRMやその他イベントの予定はこちらで見れます。
ぼくはこちらで拾ったカレンダーをgoogle calendarにインポートして使わせてもらっています。
Turbine Musings: Add Topcoder SRM Events to your calendar
SRMは開始3時間前から参加登録できます。参加者はそれぞれ、まずdiv1, div2で分かれ、その後だいたい20人ずつくらいの部屋に分けられ、対戦します。
実際のコンテストはcoding phase, intermission, challenge phase, system testの4つのフェーズに分かれます。まずは75分間のcoding phaseです。ここではひたすら問題を解きます。coding phaseが終わった後、5分間の休憩（intermission）をはさみ、10分間のchallenge phaseが始まります。challenge phaseでは他の人のコードを見ながらバグを見つけ、そのバグをつくインプットを投げるchallengeを行います。challengeが成功すると75pt加算され、失敗すると50pt減点されます。challenge phaseのあとはsystem testが行われます。system testでは問題文中のテストケースよりも多くのケースでテストされ、これに通ると点数が確定します。システムテストに落ちると、その問題の得点は0になります。
勉強、練習の方法
まずはpractice roomで過去問を解きましょう。わからない問題があった場合は、他の人のコードを読んでみます。その他にも、公式サイト上に過去問題の解説記事もアップされていて、非常に役に立ちます。
Algorithm Problem Set Analysis - TopCoder Wiki
この他にもtopcoderにはチュートリアル記事があります。
コンテストの挑み方の基本から、各アルゴリズムの解説まで多岐にわたっています。また解説だけでなく、practice roomから練習問題が提示されていることが多いので、実際に問題を解きながら学べて非常に良いです。
はじめのうちに読むといい記事をいくつか紹介すると、
- How To Dissect a TopCoder Problem Statement: 問題文の読み解き方の解説です。
- How To Find a Solution: 定番のアルゴリズムの概論を解説してくれています。
- The Importance of Algorithms: アルゴリズムの計算量などの話題です。時間の見積もりは非常に重要な要素です。
- Power up C++ with the Standard Template Library: Part I : C++使いでstlにあまり慣れていない人は、この記事で必要な機能を速習すると良いと思います。
すべて目を通した訳ではないので、他にも良い記事があるかもしれません。
日本語の記事だと、kinaba(cafelier)さんの記事が素晴らしいです。
特に(1)の実行時間の見積もりは、アルゴリズムコンテストに挑むにあたって必須です。僕もまだきちんとできてないです。
この他には、情報処理学会による、ICPC対策のための連載や、
chokudaiさんによるITmediaでの解説記事、
最強最速アルゴリズマー養成講座：あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
最強最速アルゴリズマー養成講座：オーダーを極める思考法 (1/3) - ITmedia エンタープライズ
その他ICPC向けの解説記事などがあります。
その他の情報源
- TopCoder部
- はてなグループのTopCoder部です。TopCoderに挑戦しているはてなーの皆さんの日記が読めます。慣れたらぜひ書いて見てください。ちなみに僕もここで書いてます。
- タグ「topcoder」を含む新着エントリー - はてなブックマーク
- はてブのtopcoderタグにも色々情報が集まります。
- IRCチャンネル - TopCoder部
- 参加したことはないんですが、IRCチャンネルもあるみたいです。
- Twitter / Search - #topcoder
- twitterではハッシュタグ #topcoder がよく使われています。
類似のコンテスト
- The ACM-ICPC International Collegiate Programming Contest Web Site sponsored by IBM
- アメリカの学会ACM主催の学生向けプログラミングコンテストです。おそらく世界で最も有名な大会。年に一度開催されます。
- Google Code Jam 2009
- Google主催のプログラミングコンテスト。年に一度開催。こちらは学生でなくても出場できます。
- Imagine Cup Student Competition 2010
- Microsoft主催のコンテスト。アルゴリズムだけでなく様々な種目があります。
- 天下一プログラマーコンテスト
- KLab株式会社主催の学生向けプログラミングコンテスト。今年が初年度でした。来年も開催されるかもしれません。
- EPOCH実行委員会
- 愛媛大学主催の学生向けコンテストです。
- 東京大学プログラミングコンテスト2009 (UTPC 2009)
- 東大生向けのクローズドな大会のようです。
- Project Euler
- 数学的な問題が集められたコンテスト。こちらはタイムアタックの競技ではなく、正解数を競うもののようです。
- Code Golf | Home
- こちらもタイムアタックではなく、コードの短さを競う大会です。参加者はgolferと呼ばれます。
- DouKaku?
- 公式より: 「「どう書く？org」へようこそ！このサイトは出されたお題をいかに解くか競い合う、プログラマのためのコロシアムです。 」
- パソコン甲子園2009
- 高校生向けののコンテストです。プログラミングだけでなくCGなど、様々な種目があります。
- 全国高等専門学校プログラミングコンテスト - Official Site
- 高専生むけのコンテスト。競技だけでなく、作品を提出するタイプの種目もあるようです。
- U-20プログラミング・コンテスト
- 20歳以下対象のコンテスト。作品を提出するタイプの大会のようです。
- Supercomputing Contest - Supercomputing Programing Contest Official Site
- 高校生/高専生向けのコンテスト。スパコンで問題を解くそうです。
- ICFP ’09 Programming Contest - Main Page
- どのプログラミング"言語"が最強かを決める大会らしいです。
ほかにもあるかもしれませんが、こんなところで。
Enjoy!