2016.07.27
競技プログラミングを知ろう! [第1回]
初心者から上級者まで誰でも楽しめる競技プログラミングの世界。ぜひ挑戦してみましょう。

はじめに
プログラミングコンテスト、というものを、皆さんご存知でしょうか? 単純にプログラミングコンテストというと、皆さんは様々なものを想像するかと思います。 例えば、テーマが与えられて、そのテーマに沿った作品を作るようなものだったり、ゲームの対戦AIを組んだり……。 最近だと、電王戦などもあったので、将棋や囲碁のAIを戦わせるようなものを想像する人も多いかもしれません。
ですが、今回取り扱うコンテストは、そのどれでもありません。 解くべき問題が与えられ、その問題を解けるプログラムを、早く正確に組み、 正解数や解くまでにかかった時間などを競い合うコンテストです。 いわゆる、競技プログラミングと呼ばれているものです。
さて、この競技プログラミングですが、巷では大きな誤解をされています。 プログラミングコンテストというだけあって、出るのには物凄くプログラミングを習熟していなくてはいけないだとか、 数学が分からないと挑戦ができないだとか、そんな誤解です。 ですが、実際のところは、そんなことは全くありません。 競技プログラミングは、プログラミングを始めたばかりの初心者から、 プログラミング上級者まで、誰でも楽しめるようなものです。
この連載で、競技プログラミングにぜひ挑戦してみましょう。
競技プログラミングとは
今回取り扱うプログラミングコンテストは、1時間から3時間程度で気軽に参加できるものです。 コンテストに参加するのが一般的ですが、過去のコンテストの過去問を解くことで、 練習をすることも可能です。
一般的なコンテストでは、主に以下のような流れで参加します。
1. 解く問題を選ぶ
2. 選んだ問題の問題文を読む
3. 問題文に書かれたプログラムを作成し、提出する
4. 正解判定が自動で行われ、合っていれば次の問題を選ぶ
今回は、AtCoder Beginner Contest 041をベースに、 プログラミングコンテストの参加方法を学んでいきましょう。
1. 解く問題を選ぶ
まずは、解く問題を選びましょう。とは言っても、やることは簡単です。[問題]タブをクリックして問題一覧を開いて、好きな問題を選ぶだけです。
問題一覧を開いて、好きな問題を選ぶ
コンテストにもよりますが、基本的には最初の方の問題であればあるほど、簡単な問題であることが多いです。 慣れないうちは一番上の問題から選んでいきましょう。今回の場合は「添字」という問題です。
2. 選んだ問題の問題文を読む
それでは早速問題文を読んでいきましょう。 問題文は、以下の5パートからなります。
・問題文
問題文は、解くべき問題の内容が書かれています。 今回の問題は、A問題の、「添字」という問題です。
文字列 s と整数 i (1≦i≦|s|) が与えられます。 s の i 文字目を出力してください。
なお、|s| は文字列 s の長さを表します
プログラミングコンテストに慣れていれば、この説明文だけで、簡単に問題の意味が取れると思います。 ですが、慣れないうちは、何を言っているのかわからないかもしれません。
わからなかった場合は、入出力例を確認することにより、問題の意味を正しく理解するようにしましょう。
・制約
制約は、問題文で出てきた数値や文字列に、どんな制約が与えられているかが書かれています。 AtCoderの昔の問題だと、入力のところに書かれていることも多いです。
例えば、今回の問題だと、このように書かれています。
1 ≦ |s| ≦ 100
s は英小文字のみからなる。
1 ≦ i ≦ |s|
競技プログラミングで与えられる入力は、必ずこの制約を満たしています。 ですので、提出するプログラムの中に、例外処理などを書く必要はありません。
・入力
入力は、標準入力に、どのような形式で入力される文字列が与えられるかが書かれています。 大抵の競技プログラミングのシステムにおいて、入力は標準入力から与えられます。
今回の問題だと、このような形で入力形式が書かれています。
s
i
これは、1行目に文字列sが、2行目に、与えられる整数iが与えられる、という意味です。 余計な文字列などや、誤った文字列が入力されることはありません。
・出力
出力は、標準出力に、何をどのような形式で出力するべきかが書かれています。
今回の問題だと、このような形で出力形式が書かれています。
s の i 文字目を出力せよ。
今回の場合は、出力するものが非常にシンプルですので、簡単に書かれています。 ですが、問題によっては、出力の誤差を許容したり、様々な条件がついていることもあります。 こちらもきちんと確認するようにしましょう。
・入出力例
入出力例は、実際にプログラムに与えられる入力と、プログラムが出力するべき文字列が与えられます。
今回の問題だと、例えば以下のようなものです。
入力例1
atcoder
3
出力例1
c
この入力例の場合は、「文字列"atcoder"の3文字目は何かを出力する」のが目的なので、 答えは当然'c'です。 例だけが与えられる場合もありますが、例とともに説明文が添えられていることもあります。 問題文だけで問題の理解は可能ですが、問題の理解が正しいかどうかを確認するために、 必ず入出力例は全てチェックするようにしましょう。
また、入出力例は、書いたプログラムが正しいかどうかを、簡単にチェックすることが可能です。 もちろん、入出力例の全てを正解したからといって、 そのプログラムが必ず正しいというわけではありません。 入出力例で全て正しい答えを出力できるプログラムが作成できたら、プログラムを提出しましょう。
3. 問題文に書かれたプログラムを作成し、提出する
さて、今回の競技プログラミング講座では、C++を用いて解説していきます。
今回はプログラムの内容については触れませんが、例えばこの問題だと、このようなプログラムで、 問題の要件を満たすことができます。
1 2 3 4 5 6 7 8 9 10 11 | #include<iostream> #include<string> using namespace std; int main(){ string s; int i; cin >> s >> i; cout << s[i - 1] << endl; return 0; } |
提出タブをクリックし、さっそくこのプログラムを提出してみましょう! プログラムを提出するには、AtCoderにログインする必要があります。 IDを持っていない人は、ここから登録してしまいましょう!
登録項目に難しいことはないので、今回は説明を省略します。 所属という項目に何を入れて良いか分からない、という人がいますが、そういう人は、適当な文字列を入れれば大丈夫です。 もし分からないことがあれば、Twitterの@chokudaiまでリプライを飛ばしてください。
4. 正解判定が自動で行われる
さて、このプログラムを提出すると、以下のような画像が出たかと思います。
ACという文字列が出て、正解した!
このように、ACという文字列が出れば、問題に正解したことが分かります! 他にも様々なステータスが表示されますが、それぞれ以下のような意味を持っています。
WJ → ジャッジ待ち状態です。キーボードの[F5]でリロードするなどして、ステータスを更新してみてください。
X/Y → Yケース中Xケースのテストが終了した状態です。こちらもリロードしてみてください。
WA → Wrong Answerです。出力した答えが間違っていた場合に表示されます。
RE → Runtime Errorです。プログラムがエラー終了してしまった場合に表示されます。
TLE → Time Limit Exceededです。プログラムが制限時間内に終了しなかった場合に表示されます。
AC → 正解です!
ACが出るまで、頑張って挑戦しましょう!
おわりに
さて、今回は、競技プログラミングというものが、いったいどういうものか、を説明しました。 おおよそどのようなものかのイメージがついたのではないかと思います。
競技プログラミングが難しい、と思っていた人にとっても、意外と敷居が低いことが 分かっていただけたのではないかと思います。
次回は、「競技プログラミングの何が楽しいのか?」 「競技プログラミングは役に立つのか?」など、 競技プログラミングをやるとどういう良いことがあるかの説明をしていきたいと思います。
次回の連載をお楽しみに!