TopCoder のはじめかた

０、はじめに

TopCoder とはプログラミングのコンテストのことです。
以下の記事では TopCoder の SRM について書いていきます。
SRM は１週〜２週に１回程度開催されるコンテストです。
使用できる言語は、VB、C++、C#、java の４言語です。
(２０１３年５月１日現在)
(追記：２０１３年７月より Python が追加されました。)

アカウントの登録は TopCoder のホームページで行います。
登録に必要なのは自分のメールアドレスだけです。
参加資格に特別なものはありません。
無料です。

また、大会時には java applet を使用します。
java applet が実行できる環境が必要です。
また、オンラインコンテストなので、
インターネットに接続できる環境が必要です。

１、なぜ TopCoder をやるか？

個人によって動機は違うと思いますが、
自分がやる動機は、

おもしろい問題に出会える。
英語の勉強ができる。

の２点です。

TopCoder の問題はたまにやるだけの面倒な問題もありますが、
たいていはよく考えられた質の高い問題ばかりです。
非常によく考えられており毎回感心します。

英語は読まないといけないのでなんとか読んでいます。
英語に対する拒否感が最近少し無くなってきたように思います。

もちろんプログラミングの技術も身につきます。
自分は TopCoder で再帰やＳＴＬの使い方を覚えました。
探索アルゴリズムや数値計算のやり方についても勉強しました。

楽しんで自己研鑽するにはいい場所だと思います。

２、例えばこんな問題が出る

 過去の TopCoder の問題 SRM 351 から。

１個以上、最大５０個までの数字が並んでいる。
１個の数字は１〜１０００までの数字のいずれかである。
それぞれの数字はすべて異なる。
数字はその数字の数をコストにして移動できる。
昇順に並び替えるときの最小コストを求めよ？

 例えば、

  7,1,2,3

であれば、1 と 2 と 3 を前に移動すれば昇順になる。
このときの最小コストは 1 + 2 + 3 の 6 である。

 例えば、

  7,1,2,5

であれば 7 をいちばん最後に移動すれば昇順になる。
このときの最小コストは 7 である。

 例えば、

  8,2,6,5,1,4

であれば最小コストは 18 である。

このとき、どのような数字の列であっても
最小のコストを計算して返すコードを作成せよ、
というのが問題である。

３、アカウントの登録方法について

TopCoder のサイトから登録できます。
エラーがでて登録できない、という話をよく聞きます。
ですがかならず登録できますので、
時間を変えてなんどもチャレンジしてみてください。
実際に自分も日を空けて３回ほど試して、
やっと４回目くらいに登録できたという感じです。
問い合わせのメールを送っても対応はいまいちのようです。
なぜ改善されないのかはわかりません。

４、SRM とは

開催される日時はホームページで確認できます。
アメリカのサイトなので日本時間に置き換えるのを忘れずに。
各国の時間への変換表もサイト上にあります。
開催される日時は不定期です。
印象としては日本時間で金曜の１０時頃から、
土曜日の２５時頃からはよくやる気がします。
平日の２０時頃から開催されることもあります。
昼間や夕方、早朝に開催されることはほとんどありません。
午前中か夜か深夜が多いです。
開始３時間前から参加登録できます。
java applet を立ち上げて参加登録します。
ランクは１群 div1 と２群 div2 に分けられます。
最初は div2 から始まります。
問題は Easy Medium Hard の３問です。
それぞれ得点が割り振られていて、
通常は 250 500 1000 点が割り振られています。
それぞれの問題についてどのようなケースが渡されても
２秒以内に正しい解答を返すコードを書きます。
コーディングの時間は全部で７５分あります。
各問題は開いてから提出するまでで得点が変わります。
早ければ早いほど得点は高くなります。

 提出時間と得点の目安

２５０点問題であればだいたい以下の点数です。

　３分：２４７点
１０分：２２３点
２０分：１７７点
３０分：１４２点

５００点問題ならこの倍になります。

どれだけ遅くても元の点数の３０％よりは下がりません。
２５０点問題であれば最低でも７５点は保障されます。
最初はどの問題も開かれていないので、
１つ目の問題が解けそうなら２つ目の問題は
閉じておいたほうが良いです。
問題の時間内の再提出は許されていますが、
その時間の点数より１０％が減じられます。
この場合も元の点数の３０％は保障されます。
再提出は何回でも可能です。
コーディング後に休憩が５分あります。
休憩後に１５分のチャンジタイムがあります。
チャレンジタイムは１９人の他の人が書いたコードを見て、
正確な解答を返せないと思われるパターンを送ります。
もし、正確な解答を返せなければ＋５０点。
正確な答えを返せば−２５点となります。
いちど誰かにチャレンジ成功されると、
その問題は他の人がチャレンジすることはできません。
チャレンジ成功されるとその問題の点数は０点になります。
チャレンジされることに対するペナルティはありません。
チャレンジタイムが終了すると、
運営が用意したケースとチャレンジで使用されたケースでテストし、
すべてのケースが通った時点で点数が確定します。
１つでも通らないと０点です。
部分点はありません。
順位は Easy Medium Hard の３つの問題の点数の合計と、
チャレンジタイムで獲得した点数の合計で決まります。

結果によってランクが変化します。
最初はランク 1200 からスタートします。
ランクは得点では無く順位で変動します。
１位に近いとランクは 200 くらい上がりますし、
最下位であればランクは 200 くらい下がります。
参加初期は特にランクの変動が激しいです。

ランクによって次のような呼び名がつきます

 3000 以上：ターゲット
 2200 以上：赤コーダー
 1500 以上：黄コーダー
 1200 以上：青コーダー
  900 以上：緑コードー
  900 未満：灰コーダー
ランクなし：白コーダー

最初は白コーダーです。

５、ひとつの問題の構造

どの問題も問題の表示形式は同じです。
選択する言語によって記述が異なる場合がありますが意味は同じです。
まず「Problem Statement」に問題文があります。
メモ帳などにコピー＆ペーストすると表現が変わってしまう
危険性のある問題には最初に注釈が入っています。
（例えば ２ 乗などの表記は正確にコピー＆ペーストできない。）
「Definition」には問題で作成するクラスやメソッド名、戻り値、引数の形式が書いてあります。
「Notes」には特に注意する事項が書いてあります。
「Constraints」には数字や文字のとりうる範囲などが書かれています。
「Examples」には実際に与えられる引数の例とその場合の正しい解答が書かれています。
この例は出題者のさじ加減もあるので、親切であったり不親切であったりします。

「Examples」を読むだけで問題の意味がわかる場合もありますが、
とりあえず問題文もざっと読んでおいたほうがいい気がします。

「Notes」と「Constraints」は条件の解釈に関する注意点や
与えられる数字の範囲などの定義がどうなっているかなどが書いてあります。
この部分は必ず確認する必要があると思われます。

６、プラグインの使用

TopCoder はコーディングを補助するツールがプラグインとして使用できます。
問題を開いた時点で初期テンプレートを作成するツール。
全 Example を一度に実行し結果を確認できるツール。
コードの実行速度を測定できるツール、など。
ＩＤＥと連動するなどの方法が使用できると高速にデバッグできます。
提出を１秒でも早く行いたいならプラグインの導入をお勧めします。
真面目にやるならプラグインは必須です。自分にあったものを探しましょう。

なお、プラグインを使用する場合は本番前にテストをしたほうが良いです。
本番前でも TopCoder 側で練習できる部屋が用意されます。
TopCoder の java applet が仕様を変えてくる場合があるので、
プラグインのアップデートをする必要がある場合もあるからです。

７、本戦のシュミレーション

３時間前から参加登録できるので余裕をもって登録します。
本戦の登録はホームページでなく java applet から行います。
登録してしまってから止めたくなった場合は、
問題を１問も開かなければ参加したことになりませんので、
とりあえず参加しておけば良いと思います。。
前述しましたがプラグインが正常に動くかなどを確認するため、
少なくとも１つは練習問題をやっておいたほうがいいと思います。
開始３分前くらいから部屋に入れるようになります。
この時点で参加登録は締め切られていますので、やはり参加登録は早めに。

直前には翻訳サイトや参考にできるサイトを開いておくと良い。
他の人との相談は不可だが、ウェブサイトを見たりソフトウェアを使うのは可。
すでに書いておいたコードのコピー＆ペーストも認められている。

問題は普通は Easy から解きます。
Easy は比較的早く解ける場合が多いので、
いかに早く解くかが勝負になります。
Midium は Hard を解くつもりであるかで時間配分が決まります。
Hard を解くつもりであれば Hard はかなり時間がかかるので、
少なくとも Hard を解くのに最低３０分〜４０分は残したいところです。
また、Easy が解けない場合もあるかと思われます、
この場合には Medium を解くほうが良い場合があります。
Examples があっているかのチェックができるので、
最低でも Examples はすべて通してから提出すべきです。
COMPILE → TEST → SUBMIT の順で提出する。
(TEST はとばしてもいいがテストはしておいたほうがいいと思う。)

時間が余った場合には１０％減点であるものの間違いがあれば０点なので、
すでに提出したコードの見直しをするのも良いでしょう。
また、チャレンジタイムに備えて
チャレンジケースを作成すると良いでしょう。
チャレンジケースはコーナーケースや最大のケース、
Example に用意されていないパターンのケースなど、
見逃しそうなケースを探しておきます。
(コーナーケースとは落とし穴的な見逃しやすいケースのこと)
もし、自分がその問題を解けなかったとしても、
コーナーケースや最大のケースで解法がでないことがわかるのであれば
チャレンジケースを用意することが可能です。
これはコーディング終了後の５分間でもできることです。

チャレンジタイムはコーナーケースや最大ケースなど
パッと見てわかる問題からチャレンジすると良いと思われます。
また、参加者のレートをみることもできるので、
レートの低い人のコードを狙うと良いかもしれません。
−２５点を恐れてチャレンジしないのも作戦です。
ただし、チャレンジ成功されても減点されないのでとりあえず提出しておこうというコードは多いです。
中には Example すら通って無いのに提出されたコードもあったりします。
高得点の問題に適当に当てたら落ちたというのは良くあることです。

チャレンジタイムが終わればシステムテストです。
システムテストの時間は大会によって早かったり遅かったりします。
だいたい１０分から３０分も待てば確定した順位の一覧がでます。
さらに１０分ほど待つとレートが更新されます。
アリーナを立ち上げ直せば更新されたレートがわかります。

８、Ａｒｅｎａ の使い方

SRM が開催される java applet を arena(アリーナ) と呼びます。

本戦が無いときは「Practice Rooms」から練習ができます。
「2-SRMs」から過去の問題を開くことができます。
（たまに問題を開くのに時間がかかることがあります。）
「Select one」をクリックすると 250 500 1000 の数字が出ます。
それぞれの数字を選ぶとその点数の問題を開きます。
「SUMMARY」をクリックすると提出一覧が見れます。
点数をダブルクリックすると他の人の提出したコードが見れます。
ここで「Challenge」ボタンを押すとチャレンジの練習もできます。

本戦があるときには「Active Contests」から入ります。
複数の大会が開かれている場合がありますが、
SRM であれば Single Round Match を選びます。
「Register」で参加登録をします。
「Enter」で入場しますが開始３分前くらいまで選べません。
「Registants」で参加予定者の一覧を見ることができます。
「Division Summary」は順位表です。

本戦では開始３分ほど前から「Enter」できるので、
開始前に「Enter」を選んで部屋に入ります。
部屋には２０名が割り当てられており、
チャレンジはこの部屋の他１９名に対して行われることになります。
開始時間になると、開始を知らせるウィンドウが出ます。
ウィンドウの「OK」ボタンを押して、
「Select one」から割り当てられた点数の問題を開きます。
「SUMMARY」から他の人の提出状況を見ることができます。
もちろん書いたコードは見ることができません。
残り時間は arena 上に表示されています。

チャレンジは「SUMMARY」に入って行います。
チャレンジの場合も開始を知らせるウィンドウが出ます。
ウィンドウの「OK」ボタンを押して、チャレンジを開始します。

システムテストは１０分ほどで終了します。
テストの結果は「SUMMARY」か「Division Summary」でわかります。
それから２０分ほどでレートが更新されます。
更新されたレートはいったん arena を出て入りなおすと確認できます。

本戦は参加登録をしなくても本戦の部屋に入ることができます。
もちろん登録をしないと問題をみることはできませんが、
どのくらいの速さで提出しているかを実感できると思います。

９、はじめての人へ

Div2 の Easy はコードが書ける人ならはじめての人でも解けると思います。
ただし、Div2 の Medium ははじめての人では難しいと思います。
高速に探索するアルゴリズムなどを知らないと正解できない問題がでるからです。
これは「知っている」か「知らない」かの問題なので、
あらかじめどのようなアルゴリズムが必要かを知る必要があります。
例えば、再帰関数による探索であったり２分探索であったりします。

どのような探索方法を使用するか？
探索するときにどのような高速化をほどこすか？
探索する際に使用するメモリを節約するには？

このあたりはやってみないとわかりません。
効率的な勉強法はひたすら過去の問題をやることだと思います。

過去問は大会の無いときであればいつでも自由に練習できます。

１０、実行時間２秒の対策

すべてのコードは２秒以内で解答を返す必要があります。
２秒以内で解答を返すのはおよそ最大で

５０００００００回

くらいのループが許容範囲になります。
もちろん中に書く処理の内容にもよるので、
１００００００回が限界の場合もあるし、
１００００００００回可能な場合もあります。

よって、ループの回数をあらかじめ確認することが必要です。
例えば、１０００×１０００のループは回せる、とかです。
１００００００回のループであれば２秒以内で余裕で回ります。
１００００×１００００になってしまうようであれば、
よっぽどシンプルなループで無い限り２秒を超えます。
ループの処理を削る工夫が必要です。

このとき最大のケースを考える必要があるので
問題文中の Constraints で値のとる範囲を確認します。
また、値に関する注意が Notes に書いてあるので、
ここも必ず目を通すようにします。

例えば、１〜９の数字を１０個並べるのは 9^10 通りあり、
１〜９の数字を重複無しに並べるのは 9! 通りです。

こういった計算で処理回数を調べておくと良いでしょう。
もし、値が大きすぎるならそれは普通にやっても無理ということです。

１１、メモリの使用量の対策

TopCoder では１つの問題あたりにメモリを 64MB 使用できます。
int 型であればだいたい 10000000 個くらいまで用意できます。
よって、20000000 個を用意しようとすると足らなくなります。
動的計画法などを使用する場合にメモリをたくさん使用するので、
必要に応じてメモリ量を計算しなければなりません。

メモリをたくさん使うことで高速化できるアルゴリズムもあるので、
メモリがどのくらい使えるかという情報も重要になります。

64MB というのはヒープのことです。スタックは 8MB です。
ブロック内に書くとオーバーフローする場合はグローバルにしましょう。

※2013年12月より 256MB に増えました。
以上の記述の４倍使えるようになりました。

１２、公式サイトについて

公式サイトのＵＲＬは以下です。

http://community.topcoder.com/tc

アカウントは右上の「Register」からとります。
Arena は[Algorithm(SRM)]→[Launch Arena]から起動します。
まず、ログインするので名前とパスワードが必要です。
applet での実際の練習は[Practice Rooms]で行えます。
本番は applet の[Active Contests]のところで行います。

過去問を読むだけであれば、java applet は必要ありません。
公式サイトから、
[Algorithm(SRM)]→[Match Archive] で過去の大会を選べます。
その大会のすべての問題文を読むことができます。
実際の大会で提出されたコードも読めますが、
名前とパスワードの入力が必要です。

[Algorithm(SRM)]→[Match Editorials] で過去問の解説を読めます。
すべての回ですべての解説があるわけではありませんが、
名前とパスワードを持っていなくても一部の解答例が読めます。

１３、どのくらいできればどのくらいのレートか？

Div2 でレートを落とさないためには Div2 Easy を早く解く必要があります。
Easy を 200 点台で解ければ大きくレートを落とすことは無いでしょう。
Easy を解くのが遅い、もしくは解けないとレートが落ちます。
灰コーダーから抜け出すには Div2 Easy を早く解く必要があります。
Div2 を抜け出すためには Div2 Medium を解く必要があります。
Div1 に上がるだけなら Div2 Hard が解けなくても問題ありません。
Div2 Hard が解ければレートが大きく上がるはずです。
緑コーダーの目標は Div2 Medium を解くことです。
Div1 に上がり青コーダーになると参加者の実力がいっきに上がります。
Div1 では Div1 Easy を解かないとレートを落とします。
Div1 Easy は難易度が Div2 Medium 相当かそれより難しいので、
Div2 Medium は普通に解ける必要があります。
Div1 でレートを上げようと思うと Div1 Easy を解くか、
Div1 Medium か Div1 Hard を解いていくしかありません。
Div1 Easy を確実に解くか、Div1 Medium か Div1 Hard を解いていけば
黄コーダーにはなれると思います。
赤コーダーになるには常に Div1 で５０〜１００位くらいに入る必要があります。
Div1 Easy を早く解き Div1 Medium を普通に解く、もしくは、
Div1 Easy Medium Hard を３問とも解けば赤コーダーでもレートは上がります。
ターゲットになると最低でも Div1 で１０位以内に入り、
１０位以内に入ることを継続していかないとレートが落ちます。

１４、問題の難易度

Div2 Easy

「直感的に解く」か「総当りで解く」のいずれかが通用します。
メモリや速度を気にしなくても解ける場合がほとんどです。
ルールがわかってコードが書ければ正解を出すことができます。

Div2 Medium

深さ優先探索、幅優先探索、順列、ビット探索、２分探索、動的計画法など。
なんらかの工夫か特殊なアルゴリズムを使わないと解けません。
過去問を見ての対策が必要です。直感でやってもまず解けません。
初心者にとっては最初の大きな難関です。

Div2 Hard

数学の仕組みを使った場合の数、動的計画法の問題が多いです。
複雑な実装やグラフ、幾何もたまに出ることがあります。
ごくまれに驚くほど簡単な問題が出題されることがあります。
とりあえず読んでおいて損はありません。

Div1 Easy

Div2 Medium と同じか条件を難しくした問題がよく出ます。
ルールがより複雑になるので実装ミスが多くなります。
ただし、基本的には短いコードで書ける場合がほとんどです。
幾何、動的計画法、グラフなどの問題はほとんど出ません。

Div1 Medium
貪欲、全探索、数学、幾何、動的計画法、グラフなどバラエティ豊かです。
幅広いジャンルで問題を解けるようにならないと解くのは難しいです。

Div1 Hard

高難度の動的計画法、グラフの問題がよく出題されます。
記述するコードも長くなるので最難関といえるのではないでしょうか。

１５、ＴｏｐＣｏｄｅｒ用語集

ＳＲＭ・・・ＳｉｎｇｌｅＲｏｕｎｄＭａｔｃｈ。定期的に行われる大会のこと。
Ｄｉｖ１、Ｄｉｖ２・・・１群、２群のこと。
ａｒｅｎａ・・・アリーナ。大会が行われるアプレット。
Ｃｈａｌｌｅｎｇｅ・・・他のコードに適切な解答を返さないと思われるケースを試すこと。
ＴＬＥ・・・ＴｉｍｅＬｉｍｉｔＥｘｃｅｅｄｅｄ。制限時間の２秒オーバーのこと。
ＷＡ・・・ＷｒｏｎｇＡｎｓｗｅｒ。コードが間違っていてシステムテストを落とすこと。

ＤＦＳ・・・深さ優先探索。
ＢＦＳ・・・幅優先探索。
Ｇｒｅｅｄｙ・・・グリーディ。貪欲法。優先だと思われる方法をどんどん試す方法。
ＢｒｕｔｅＦｏｒｃｅ・・・ブルートフォース。全探索のこと。
再帰・・・再帰関数。もしくは再帰を使って問題を解くこと。
メモ化・・・メモリに値をメモして更新して問題を解いていくこと。
ＤＰ・・・ＤｙｎａｍｉｃＰｒｏｇｒａｍｉｎｇ。動的計画法。アルゴリズムの名前。
グラフ・・・データの状態。もしくはそのデータ構造を使って問題を解くこと。
幾何・・・図形を使って数学的に解く問題のこと。