競技プログラミングとは
競技プログラミング（英語: Competitive programming、略称: 競プロ）とは、プログラミングコンテストで行われる競技の一種である。(Wikipediaより)
なぜ競技プログラミング？
前職と違い、今の会社は周りにいるエンジニアが超少ないです。
つまり、自分の力を測る物差しがないのです。
そうでなくとも客観的な視点で自分の評価をしてほしいという思いは以前からあり、前職時代は始めようと蟻本まで買ったものの、時間がなく放置していました。
今の職場は幸い時間は自由なので、挑戦してみようと思った次第です。
最も有名な競技プログラミング「TopCoder」
僕の中では「競技プログラミングといえばこれ」といったイメージです。
競技に参加すると、自分の実力を表すレートが計算され、レートによって色でクラス分けされます。
公式によると、以下のようにクラス分けされるようです。
また、色でのクラス分けの他に、レートによってDivision1, Division2にクラス分けされます。
レートが1200以上であればDivision1、レートが1200未満かレートが付与されていない人はDivision2となり、Division1のほうが難しい問題が出題されるようです。
赤色の人はRed Coderと呼ばれ畏怖される(?)存在になれます。
最終目標はもちろん赤色ですね。かっこいい。
TopCoderは様々な競技方式で競技を開催していますが、最も一般的にはSRMという競技方式です。
SRM
SRMでは以下の４つのフェーズをこなすことになります。
- Registration
- Coding Phase
- Challenge Phase
- System Testing Phase
それぞれのフェーズについて、公式サイトの記述に基いて概要をまとめておきます。
なお、SRMはSingle Round Matchの略です。
Registration
このフェーズではSRMへの参加を意思表示します。
In order to compete in the SRM, all competitors must register and possibly answer a brief survey question. Registration begins 3 hours before the match starts, until 5 minutes before a match begins. To avoid issues, it is generally recommended to register at least 15 minutes before a match is scheduled to begin.
開始３時間前から受付を開始し、５分前に締め切られます。
公式では、余裕を持って１５分前には登録することを推奨しているようです。
Coding Phase
SRMのメインフェーズですね。
The Coding Phase is a timed event where all contestants are presented with the same three questions representing three levels of complexity and, accordingly, three maximum point values. Points for a problem are awarded upon submission of any solution that successfully compiles, and are based on the total time elapsed from the time the problem was opened until the time it was submitted. The Coding Phase lasts 75 minutes.
コーディングフェーズでは、３種類のレベルの問題が参加者全員に出題されます。
それぞれの問題にポイントが付与されています。
ポイントは正常にコンパイルされたコードを提出した段階で参加者にされます。 なお、問題を開いてから提出するまでの時間に応じて付与されるポイントが決まります。
コーディングフェーズは75分間です。
Challenge Phase
チャレンジフェーズは他人のコードを読む良い機会となります。
The Challenge Phase is a timed event wherein each competitor has a chance to challenge the functionality of other competitors’ code by providing an input that will cause the competitor’s code to produce the wrong output, throw an error, exceed the time limit, or otherwise fail in some way. A successful challenge will result in a loss of the original problem submission points by the defendant, and a 50-point reward for the challenger. Unsuccessful challengers will incur a point reduction of 25 points as a penalty, applied against their total score in that round of competition. If a competitor should ever attain a negative point total, that individual will no longer be able to make challenge attempts. The Challenge Phase lasts 15 minutes.
チャレンジフェーズでは他人のコードのあらをさがして、正常にパスしないようなテストケースを与えます。
チャレンジが成功すると、他人の獲得ポイントを無効にでき、かつ自分は撃墜ポイント50ptを得ることができます。
しかし、チャレンジ失敗は-25ptとなります。
チャレンジは自分のポイントが余っているときにしかできません。
チャレンジフェーズは15分間です。
System Testing Phase
The System Testing Phase is applied to all submitted code that has not already been successfully challenged. If the Topcoder System Test finds code that is flawed, the author of that code submission will lose all of the points that were originally earned for that code submission. The automated tester will apply a set of inputs, expecting the output from the code submission to be correct. If the output from a coder’s submission does not match the expected output, the submission is considered flawed. If any test case causes a submission to exceed the runtime limit, or produce an error, that is also a failure. The same set of input/output test cases will be applied to all code submissions for a given problem. All successful challenges from the Challenge Phase will be added to the sets of inputs for the System Testing Phase.
チャレンジが成功していない(=生き残っているコード)全てに対してシステムチェックが行われます。
ここでこけると、そのコードで獲得したポイントは全て失われます。
TopCoder公式が用意したテストケースの他、成功したチャレンジのテストケースでもチェックが行われます。
ここが通過できれば晴れてポイント確定となります。
まとめると・・・
コーディングフェーズでは速く的確にコードを書くことが必要になります。
ただし、間違えると結局ポイントは得られないので、速さよりは正確さに重点を置いたほうが良さそうです。
チャレンジでは失敗するとマイナスポイントを喰らってしまうので慎重に行いましょう。
開催時期
公式によると、月に2-4回開催されるそうです。
開催スケジュールはEvent calendarから確認可能です。
右下の+Googleカレンダーボタンを押すことでグーグルカレンダーに登録することができます。
グーグルカレンダーに登録すると自動的に日本時間での表示になります。
目標
競技プログラミングを行うことで、以下のことが身につくことを期待しています。
- アルゴリズムの知識
- 頭の回転の速さ
- 他人のコードを読む力
また、冒頭に述べた通り、客観的な評価(レート)を得ることができます。
今年中に黄色まで行きたいなぁ。