エンジニアのスポーツ「競技プログラミング」を実際に体験してみた

「競技プログラミング」とは、出題される問題を制限時間内に解くプログラムを作成するスピードを争う競技で、プログラミングを使ってパズルを解くスポーツと表現されることもある競技です。今回は競技プログラミングに参加するための環境を構築し、コンテストの過去問を解いてみました。

AtCoder
http://atcoder.jp/

今回はAtCoderというサイトを使います。トップページへアクセスし、右上の「新規登録」をクリック。

ユーザーID、メールアドレス、パスワードなどを記入し、「個人情報の取り扱いについて確認しました」にチェックを入れて「新規登録」をクリックします。

登録が完了したら「practice contestに参加する」というボタンが表示されるのでクリックします。

画面上部に「Joined in～」という文字が出たのを確認し、上のタブから「問題」をクリックします。

つづいて「はじめてのあっとこーだー」をクリック。

問題ページに移動すると、「問題文」が表示されます。今回の問題文は「整数a,b,cと、文字列sが与えられます。整数a+b+cと、文字列sを並べて表示しなさい」というもの。競技プログラミングとは、このような形で出題される問題を解くプログラムを作る早さを争う競技です。

問題文の下には「入力」の詳細な形式と「出力」のあるべき形式がそれぞれ表示されています。

問題文がよく理解できなくても、ページの下部に付いている「入力例」と「出力例」が理解を助けてくれます。下の画像を見れば分かるように、上三つの数字を足した値と最後の文字列を組み合わせて出力すればいいことが分かります。

例は通常3つ程度用意されているので、問題文を読んでよく分からなかったらまず例を見るのもおすすめです。今回するべきことが分かったので、早速プログラムを組んでいきます。

まっすぐプログラミングに突入したかったのですが、書き上げたプログラムを実行するにはコンパイラと呼ばれるソフトウェアが必要です。今回はMinGWというコンパイラを使用します。MinGW公式サイトへ行き、右上にある「Download Installer」をクリックします。

すると、SourceForgeのダウンロードページへ自動的に遷移し、「mingw-get-setup.exe」のダウンロードが始まります。

ダウンロードが完了したらダブルクリックしてファイルを実行します。

インストーラーが起動したら「Install」をクリックします。

設定を確認し、そのまま「Continue」をクリック。設定を変更する必要は基本的にありません。

ダウンロードが始まるのでしばらく待ちます。

緑色のプログレスバーが右端まで行けばダウンロードは完了。「Continue」をクリック。

「MinGW Installation Manager」が起動するので「mingw32-gcc-g++」の横にあるチェックボックスをクリックし、「Mark for Installation」をクリックします。

同じようにして「mingw32-base」のチェックボックスにも印を付けます。これで2つのチェックボックスにマークが入っている状態です。

次に左上の「Installation」メニューから「Apply Changes」をクリックします。

「確認画面が出るので「Apply」をクリック。

インストールに10分ほどかかります。インストールが完了したら右上にある「Close」ボタンをクリックしてウィンドウを閉じます。

続いて「パスを通す」という作業を行っていきます。「Winキー＋E」でエクスプローラーを開き、左の「PC」を右クリックして出てくるメニューの一番下にある「プロパティ」をクリックします。

左のメニューから「システムの詳細設定」をクリック。

「システムのプロパティ」というメニューが出るので、一番下の「環境変数」をクリックします。

「環境変数」メニューが開くので、「Path」をクリックして選択した後「編集」をクリックします。

右上の「新規」をクリックし、「MinGWのインストールフォルダ\bin」と入力して「OK」をクリックします。MinGWを標準設定のままインストールした場合は下の画像のように「C:\MinGW\bin」と入力すればOK。

「Winキー＋R」で「ファイル名を指定して実行」メニューを開き、名前に「cmd」と打ち込んで「OK」をクリックします。

コマンドプロンプトが開くので、

g++ -v

と入力してEnterキーを押します。下の画像のような文字列が表示されれば成功です。もし「'g++'は、内部コマンドまたは～」という文章が出てきてしまった場合、環境変数の設定が間違っている可能性が高いのでもう一度確認してみてください。

コマンドプロンプトは開いたままにしておき、続いて作業フォルダを作成します。デスクトップに「kyopro」というフォルダを作り、フォルダの中を右クリックして出てきたメニューから「新規作成」→「テキスト文章」をクリックします。

ここで、エクスプローラーの上のタブから「表示」を選び、「ファイル名拡張子」にチェックを入れておきます。既に入っている場合はそのままでOK。

作られたテキストドキュメントを選択した状態で「F2」キーを押し、「practice.cpp」にリネームします。

拡張子を変更する際に警告がでるので「はい」をクリック。

「practice.cpp」をダブルクリックすると、「このファイルを開く方法を選んで下さい」というポップアップが表示されるので、「メモ帳」を選んで「OK」をクリックします。今回はこのままメモ帳で進めていきますが、テキストエディタとして使いやすいものではないので、お好みのテキストエディタを使えばOKです。

まずは以下のコードをコピーして……

#include <iostream>

using namespace std;


int main(){

    ////////////////////////
    この部分にコードを書いていく
    ////////////////////////
    return 0;

}

先ほど作った「practice.cpp」に貼り付けます。

基本的には「この部分にコードを書いていく」の部分を編集すればOK。たとえば、入力された数字をそのまま出力するプログラムは下のとおりです。

int a;

cin >> a;

cout << a << endl;

コマンドプロンプトに

cd Desktop/kyopro

と入力して先ほど作成した「kyopro」ディレクトリに移動します。移動したら

g++ practice.cpp

と入力し、ソースコードをコンパイルして実行ファイルを生成します。

「kyopro」フォルダを見ると、「a.exe」という名前の実行ファイルが生成されたのが確認できます。

コマンドプロンプトに戻り、

a

と入力すると「a.exe」が実行されます。自動的に入力待ち状態になるため、何か数字を打ってEnterキーを押すと入力した数字が返ってきます。「0」と入力すると「0」が返ってきて、「1000」なら「1000」、「3456789」なら「3456789」が返ってきました。

準備完了です。早速問題に手を付けていきます。問題を再確認すると、順に3つの数字が与えられるのでそれを足し合わせ、最後に入力される文字列と一緒に出力するというものでした。

解答となるコードを書き上げます。

コードができたら、再び

g++ practice.cpp

と入力してコンパイルします。続いて

a

と入力し、a.exeを実行します。入力待ち状態になったら、AtCoderの問題ページにあった「入力例」の通りに

1
2 3
test

と入力してみると、その下の行に「6 test」と出力がありました。これは「出力例」の通りなので先ほどのコードは正解だと考えられます。

なお、入力はコマンドプロンプト上で直接入力する他にも、テキストファイルから入力することもできます。作業フォルダに「input.txt」というファイルを作って入力したい内容を書いて保存し……

「a」を実行する際に、

a < input.txt

のように入力するとテキストファイルから入力できます。

さて、正解と確信が持てるコードができたらAtCoderに提出します。practice.cppの中身を全文コピーして……

AtCoder上の「提出」タブを開いた先にある「ソースコード」の部分に貼り付けます。問題が「A-はじめてのあっとこーだー」、言語が「C++14」となっていることを確認し、一番下の「ソースコードを提出する」をクリック。

提出が受け付けられました。「WJ」とはWaiting for Judgeの略で、つまり採点待ちということです。

1分ほどしてからページをリロードしてみると、「WJ」だった状態が「AC」に変化しました。「AC」とはAcceptedの略で、つまり正解ということです。

過去のコンテストで実際に出題された問題に挑戦してみます。上のナビゲーションバーから「コンテスト」ページを開き、「過去のコンテスト」から「AtCoder Beginner Contest」を選択し、表示された「AtCoder Beginner Contest 081」をクリックしました。

「AtCoder Beginner Contest」は初心者向けのコンテストで、易しくて教育的な問題が出題されます。早速「問題」タブに移動して問題を見てみます。

まずは「A」問題から。一番上の「Placing Marbles」をクリックします。

問題名は英語でしたが、問題文は日本語なので英語が苦手な人でも安心です。

問題文の下には入力と出力の形式が定義されています。

どの問題にも「入力と出力の例」が付いているので、日本語も苦手という人でも安心です。例1を見ると入力が「101」の時の出力は「2」とのこと。「マス1,3にビー玉が置かれます」という説明文も付いています。

2つ目の例を見ると、入力が「000」の時は「0」が出力されるとのこと。つまり、入力には「0」か「1」が3つ入り、そのうち「1」の個数が出力されればいいようです。

問題が解けたところでコードを書き上げます。

上の画像のコードを「beginner081a.cpp」という名前で保存し、

g++ beginner081a.cpp

と入力してコンパイルします。するとなにやらエラーが出てしまいました。「"1"」の部分に下線が引いてあり、ここに問題がありそうです。

調べてみると、ダブルクォーテーションは文字が格納されているアドレスを示すポインターで、シングルクォーテーションで囲むのが正しいとのこと。

気を取り直してコンパイルし、生成されたa.exeを実行して例にあった通り「101」と入力すると「4201133」と返ってきてしまいました。

理由はansを宣言した時に「0」を代入していなかったため。今度はちゃんと初期化します。

修正したコードをコンパイルし、例の通り「101」と「000」を入力してみると、それぞれ「2」と「0」という答えが返ってきました。これで大丈夫そうです。

コードを全てコピーし……

AtCoderの問題ページの一番下にある「提出する」ボタンをクリック。

「ソースコード」欄にコードを貼り付け、「ソースコードを提出する」をクリックします。

しばらく採点を待ち、リロードしてみると「AC」となっていました。これで1問正解。

再び「問題」タブから今度はB問題の「Shift only」をクリックします。

問題文と……

入力と出力の形式が与えられます。

問題文が難しくても例があるので安心です。「全ての数字を2で割る」という操作を何回行えるか？という問題のようです。

奇数があるときは一回も操作を行えません。

問題Aは3桁でしたが、今度は大きい数字が与えられることもあるようです。

とりあえず入力を取り込む部分を作成しました。入力される値のそれぞれを配列aに追加していきます。

「それぞれの入力が何回2で割れるか」を計算し、その最小値を出力することにしました。half(x)の戻り値に「xが何回2で割れたか」が入るようにします。

という訳で用意したhalf関数がコレ。奇数だったら0を返し、偶数だったらもう一度halfに送ってその戻り値に1を足すという再帰関数です。

手元でテストするために入力例1をコピーし……

「input1.txt」という名前で保存します。

同じ要領で「input2.txt」と「input3.txt」を作成しました。

コンパイルしてみると、エラーが出てしまいました。「}」が抜けているとのことだったので……

抜けていた閉じ括弧を追記します。

もう一度コンパイルして実行し、三つの例それぞれの入力を流し込むと「2」「0」「8」と出力されました。これで良さそうです。

AtCoderの問題ページの一番下にある「提出」ボタンをクリックし……

ソースコードを貼り付けて「ソースコードを提出する」ボタンをクリックします。

しばらく待ってから結果ページをリロードしてみると、無事「AC」と表示されました。これで2問正解です。

この調子でC問題の「Not so Diverse」に挑戦してみます。

問題文はこの通り。「N個のボールに書かれている数字の種類をK種類以下にするには何個のボールを書き換える必要があるか？」という問題です。

問題文の下には入力と出力の形式が続きます。

入力例1は

5 2
1 1 2 2 5

となっており、5個のボールに「1」「1」「2」「2」「5」と3種類の文字が書かれている時に、数字の種類を2種類以下にするには「5」が書かれているボール一つだけを書き換えれば良いので「1」を出力します。

例2も見てみます。数字の種類を4種類以下にしなければなりませんが、もともと2種類しか無いので「0」を出力するとのこと。

3つ目の例もありました。ひとまず、先ほどと同じように全ての例を「input1.txt」「input2.txt」「input3.txt」に保存します。

迷走しながらも、なんとかコードを書き上げました。

コンパイルして実行すると、「1」「0」「3」という求めていた答えが返ってきました。このまま提出します。

AtCoderの問題ページの一番下にある「提出する」ボタンをクリックし……

ソースコードを貼り付けて「ソースコードを提出する」ボタンをクリックします。

しばらく待ってから結果ページをリロードすると、無事「AC」が表示されました。しかし、実行時間が「1271ms」もかかってしまっています。実は、競技プログラミングには実行時間の制限があり、多くの問題は実行時間が2000ms(2秒)を超えると不正解になってしまいます。上位の問題では「いかに少ない計算量で答えを求めるか」という別次元の戦いが繰り広げられます。

終了したコンテストの場合、他の人が提出したコードが全て公開されているのでそのコードを見て勉強することができます。「結果」タブから「すべての結果」をクリックします。

問題名を「C - Not so～」、言語を「C++14」、状態を「AC」にして「検索する」をクリックし、次に「実行時間」をクリックして実行時間が短い方から順に並べます。とりあえず一番上に来た人のコードを見てみるので、一番上の「詳細を確認」をクリックします。

下のようなコードが表示されました。これを解読してみます。

なお、「解説」タブの「解説」をクリックすると……

問題を解説したPDFファイルをダウンロードすることができます。

C問題の解説が簡潔に書かれていました。

成績上位者のソースコードと公式の解説PDFから分かったことを「5」「2」「5」「3」「1」「2」「5」「5」という入力を例にしてまとめたものが下の画像です。8個の入力を2種類以下にする場合を考えています。上位者のソースコードの「cin >> a;」の下にある「cnt[a]++;」はどの数字が何回登場したかを数えています。これが図で言う二つ目、左端にcnt」と書かれているブロックにあたります。図の例でいうと「1」が1回、「2」が2回、「3」が1回、「4」は0回、「5」は4回登場したというように記録されます。その後、sort関数を使ってcntをソートし、1回以上登場した数字が何種類あったかをgに記録します。今ある種類数からkを引くことで、何種類の数字を変えないといけないかを計算し、cntの0じゃない部分の小さい方からg-k個分足し合わせたものが答えになります。今回の例で言うと、並べ替えたcntの0ではない部分の下から4-2=2個分を足し合わせた数字、つまり1+1=2が答えとなります。

どのように答えが導き出されるかというアルゴリズムが分かったので、上位者のソースコードを参考にしつつコードを書いてみます。

コンパイルしてみると、「sortという関数が存在しない」というエラーと、「gという変数が存在しない」というエラーが出ました。

「g」は自分で書いていたコードでは「types」という名前になっていたので「types」に修正します。

C++のsortについて調べると、ソースコードの先頭に

#include <algorithm>

と書く必要があるようです。

というわけでサクッと修正。

修正したらコンパイルできたので問題ページにある「例」の入力を試してみます。「例1」の出力は「1」でないといけないのですが、なぜか「0」になってしまっています。

原因を調査するために数字を読み込むたびに「cnt[a]」を出力するようにしてみます。

コンパイルして実行してみると、「4199636」という謎の数値が出力されました。

よくコードを観察すると配列外参照が起きていました。

int cnt[5] = {};

と宣言した場合、アクセスする際に使う数字はcnt[0]～cnt[4]のように0から4になるのでcnt[5]を使用しようとしてバグが起きたということです。

修正したので再びコンパイルして実行します。デバッグ用の出力文を消し忘れていたためいろいろ出力されていますが、最後に出てくるのが答えのはずなので、「0」になっているのはまだ何かがおかしいということです。

数字の種類数をチェックする際、0からn-1番目までしかチェックできていませんでした。n番目までチェックするように修正します。ついでにデバッグ用の出力も消しておきます。

もう一度コンパイルして実行してみると、こんどは「1」「0」「3」とあるべき数字が出力されました。

ソースコードを提出します。

結果を見てみると、先ほどは「1271ms」かかっていた実行時間が「80ms」まで減らせています。

なお、「順位表」タブを見れば分かるように、このコンテストの制限時間内にD問題を解けた人は25人しかいません。D問題はかなり難しいので、最初のうちはしばらく考えて分からなかったら解説を見た方がいいかもしれません。動的計画法やいもす法、ツリーや二分探索など競技プログラミングに頻出のアルゴリズムが登場します。なお、C問題まで解けた人は397人いました。

D問題の問題文を見てみると、操作量に「2N回以下」という制約が課せられており、いかにしてこの制約をクリアできるか、という問題のようです。自信のある方はぜひチャレンジしてみてください。

AtCoder Beginner Contestは毎週土曜日か日曜日の21時から22時40分まで行われています。解説放送も行われるなど、初心者が挑戦しやすいコンテストとなっているので、競技プログラミングを始めてみたいという人にはオススメのコンテストとなっています。