あなたの論理的思考とコーディング力は3倍高められる：最強最速アルゴリズマー養成講座（1/2 ページ）

全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。

[高橋直大，ITmedia]

はじめに

　はじめまして。高橋直大です。本連載「最強最速アルゴリズマー養成講座」では、全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」について、そこで出題される数学・アルゴリズムのパズルを考えることで、コーディングのテクニックおよび論理的思考力を磨くことを目的に開始するものです。ここで扱う技法は主にアルゴリズムのそれですが、その根底にはロジカルな思考術が存在します。そうした能力を養いたい方にとって少しでも役に立てれば幸いです。

　なお、本稿は必要に応じてコーディング例も紹介しますが、TopCoderで出題される問題の中から比較的やさしい問題を選択しますので、それほど実装が重たいわけというわけではありません。むしろ、論理的に考えられるかどうかが重要な要素となります。プログラミングスキルがあるにこしたことはありませんが、プログラミング経験がない方、もしくは初心者の方であってもパズルを解く感じでチャレンジしてみてほしいと思います。

TopCoder SRMとは

　TopCoderがプログラミングコンテストであることはご存じの方も多いと思いますが、これは総称であり、実際には幾つかの部門が用意されています。この中で、わたしがよく挑戦するのがアルゴリズム部門のSRM（Single Round Match）と呼ばれる部門です。だいたい半月に1度開催されるSRMでは、約1時間の時間内でアルゴリズムにかんする問題を3問解くというものです。java／C#／C++／VBなどの言語が利用可能ですので、自分の得意な言語を用いればよいでしょう。

　SRMは、大きく分けると3つのフェーズで構成されています。以下、それぞれのフェーズについて紹介します。

Coding phase

　Coding phaseは、出題される問題を解く時間となっています。問題は、点数が異なる（難易度の異なる）3問の問題が用意されおり、どの問題から取り組んでも構いません。問題を解くための実装をコーディングして、submitするのが基本的な流れとなります。submitが早ければ早いほど獲得できる点数が高くなりますが、何度もsubmitすると点数にペナルティがあります。

Challange phase

　休憩を挟むとChallange phaseと呼ばれるフェーズがはじまります。このフェーズではほかの参加者のコードを見ることができ、他人のバグを顕在化させるテストケースを送りつけることで自分に点数が入る仕組みとなっています。ただし、チャレンジに失敗すると点数にペナルティがあります。

System testing phase

　システムが各参加者のコードをテストするフェーズです。テストに失敗したら点数は没収されます。ここでは特にやることはなく、しばらく待っていると最終的な成績が出ます。

　TopCoderの参加者は成績を基に6段階にレーティングされ、これが実力の指標となります。レーティングの高いものから、Red、Yellow、Blue、Green、Grey、Whiteと色で分けられ、画面上のユーザー名などはこのレーティングの色に沿って表示されるので、参加者のおおよそのレベルが一目で分かるようになっています。また、レーティングを用いて、1200を境に上位がDivision1、下位がDivision2と2つのグループに分けられ、実力に合わせた問題が出題される仕組みになっています。

　このうち、最上位のRedレーティングは登録者比で上位0.2％程度しか存在しない、まさに選ばれしコーダーであり、いわゆるRedcoderと呼ばれています。「“赤いヤツ”は3倍早い」というのはアニメだけの話ではありません。Redcoderは、素早く、しかし確実に華麗なコードを書き上げ、上述したChallange phaseでは容赦なく他人を撃墜していく存在であり、参戦者からすると恐怖の対象でもあります。名実ともに世界で認められた存在だといってもよいでしょう。

　以上がアルゴリズム部門のSRMの大まかな流れとなります。では、次のページから実際の問題についてみていきましょう。