はむ吉(のんびり)の練習ノート

プログラミングとことばに関する話題を中心に,思いついたこと,試してみたこと,学んだことを,覚え書きを兼ねてまとめます.その際に役立った,技術書,参考書,辞書,機器などの紹介も行います.

はじめてのTopCoder Single Round Match

Single Round Match (SRM)は、TopCoderにおいて1週間に1回程度行われる競技プログラミングのコンテストです。1月20日21時(日本時間)から、SRM 679が開催され、私はそれに参加しました。これは私にとってSRMへの初参加でした。この記事では、一般的なSRMの流れについて述べつつ、その顛末や、感想について述べます。

SRM 679への参加に至るまで

SRMの存在についてはかねて知っていましたが、おそらく私がまともに使える唯一の言語であろうPythonでは解答できないと思い込んでおり、参加を躊躇していました。しかしながら、よく調べたところ、Python 2.xであれば使用できることを知りました。そこで、できれば試しに参加してみたいと思いました。実のところ、それから数日はSRMのことを忘れていました。ところが、上述のSRM 679の登録が締め切られる数十分前になって、とあるツイートによりSRMのことを思い出し、慌てて登録手続きを行いました。事前に「g:topcoder:keyword:SRMに参加」という解説*1を一読していたため、初めてではありましたが、無事に手続きを終えることができました。なお、このような状況のため、事前に過去問を解くといった準備はほとんどできていませんでした。

SRM 679中の様子

SRMへ参加する際に、Ratingが1200以上の人はDivision 1に、Ratingが1200未満の人および(私のように)Ratingをまだ付与されていない人はDivision 2に振り分けられます。Divisionにより出題される問題が異なります。各Divisionにおいて、さらに参加者はいくつかのRoomに配置されます。

また、上掲の解説にも記載されているように、SRMは次のフェーズに分かれています。

  1. Coding Phase(答案の作成)
  2. Intermission(休憩)
  3. Challenge Phase(参加者間における答案の誤りの指摘)
  4. System Testing Phase(システムによる答案のテスト)

Coding Phase

Coding Phaseでは、3つの問題が与えられ、これに対する答案を作成して提出することが求められます。これらの問題は、難易度に応じてEasy, MediumおよびHardと呼ばれることが一般的であるようです。私はEasy(配点250)について答案を提出できました。しかしながら、Medium(配点500)については大まかな解法が浮かんだものの、時間内にうまく実装できませんでした。また、Hard(配点1000)については問題文を読みましたが、もはやそれ以上何もできませんでした。なお、問題文は当然ながらすべて英語で書かれていました。とはいえ、比較的平易な単語を用いて、しかも丁寧に記されていたため、問題の趣旨を理解するのにあまり支障はありませんでした。

Challenge Phase

Challenge Phaseでは、各Roomにおいて参加者が他の参加者に対してチャレンジを行えます*2。私の答案は、幸いにもチャレンジを受けずに済みました。逆に、私が他の参加者にチャレンジをすることもありませんでした。もしかすると誤答ではないだろうかと思った答案はありましたが、どうも確証を持てなかったため、チャレンジを見送りました。チャレンジにもコツがいると感じました。

System Testing Phase

System Testing Phaseでは、答案の正誤がシステムにより判定されます。このフェーズをもって、各人の得点が確定します。私の答案はこのフェーズを無事に通過しました。

SRM 679の結果

私の得点は130.60点でした。また、順位はDiv. 2全体で270/656であり、Room内で7/20でした。このSRMによって、私のRatingは1126となりました。

Arenaのユーザインタフェースに対する感想

私が慣れていないせいもあるのかもしれませんが、SRMへの参加に用いたArenaというシステムの画面は、やや操作しにくいものであると感じました。たとえば、ボタンのクリックをはじめとする操作から画面の変化までに数秒の間隔が空くことがしばしばありました。そのため、私が操作を誤っているのか、それともただ処理に時間がかかっているだけなのか見分けるのが困難でした。世界中から大勢参加するコンテストなので、そのようなもたつきは、やむを得ないものなのかもしれませんが。

今後の課題

今回のSRMを通じて、コンテストでより多くの問題に解答できるようになるためには、アルゴリズムの学習を進めることだけではなく、解法を実装する力を培うことも必要であると認識しました。今後は、この点を踏まえつつ、コンテストの過去問やオンラインジャッジなどを利用して練習していきたいと考えています。

*1:TopCoderへの登録方法や、SRMへの参加およびその各フェーズについて詳しく書かれており、大いに参考になりました。この記事が書かれた際のTopCoderの画面は、現在のそれとはいくぶん違いますが、大まかな流れはほぼ同じのようでした。

*2:大まかに言うと、このフェーズで参加者は同じRoomに属する他の参加者による答案の誤答を指摘できます。その指摘が正しければ追加点が得られますが、さもなければ減点されます。