シリーズ目次
0: C++を書けるようになる
1: 競技プログラミングとは? ←この記事
この記事について
こんにちは。大学1年のZOIです。高校の後半で競技プログラミングにハマったので、布教用に記事を書きます。
完全に初心者の人は、ひとつ前の記事と見比べながら読み進めるとよいかもしれません。
競プロといってもAtCoderしか扱いません。
「競プロをやったことがない」「アカウントは作ったけど何もわからない」くらいの人を対象にしています。
僕もガチ勢ではないので、AtCoderで色を持ってるレベルの人はぜひ記事のミスを見つけて教えて下さい。
競技プログラミング(競プロ)って何?
例えばこんな問題や、
こんな問題が出ます。
これを解くプログラムを書いて送信する、というゲームです。
このようなゲームを開催しているサイトは複数あるのですが、日本語でやるならとりあえずAtCoderを選べば問題ないので、以下ではAtCoderの話をします。
必要なもの
とりあえず始める、ということなら、小学校〜中学校レベルの算数・数学ができればどうにかなります。
あとは、パソコン・ネット回線が必要です。また、コンテストが主に土曜日の夜9時から始まるので、その時間が空いていないとレート(レベルのようなもの)が上がりません。せめて月1回くらいは空いていてほしいです。
プログラミングの知識についてですが、学校の授業、オンラインのサイトなど何でもよいので、変数、型(int, double, bool, string)、if文、for文くらいは抑えていてほしいです。
この記事ではC++を利用しますが、PyhtonやJavaScriptなど、どの言語でもAtCoderに参加できます。
解いてみる
まずはこの問題を解いてみましょう。
ABC086-A Productという問題です。
解き方はわかると思います。$a$、$b$の2数が与えられるので、$a\times b$を2で割ったあまりが0であればEven、1であればOddと出力すればよいです。AtCoDeer君は解く上では何も関係ありません。
別解
$a$、$b$のうちいずれか一方が偶数なら`Even`、そうでなければ`Odd`、でもよいです。まずは、与えられるaやbを受け取ります。
int a;でaという変数を作る(中身はint(整数)が入っている)という意味になります。
int a, b;で、int a; int b;を一行で書けます。
cin >> a;で、入力されたものをaに入れる、ということができます。
今回、a→bの順で入力されるので、cin >> a >> b;と書くことで、一行で入力を受け取れます。
次に判定です。四則演算は+ - * / で、あまりの計算が%なので、%を使えばこの問題が解けそうです。
出力は、cout << a << endl;と書くことで、aを出力して改行、ということになります。
AtCoderでは、基本、答えの最後は改行で終わるようにしましょう。
以上をまとめると、例えばこのようなコードが答えです。
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
if(a*b % 2 == 0) cout << "Even" << endl;
else cout << "Odd" << endl;
}
AtCoderアカウントを作ってから問題のページにアクセスし、下の提出欄にコードを張り付けて提出すれば、自動で実行して採点されます。
言語欄には「C++20(gcc 12.2)」を指定しておけば大丈夫です。
提出結果ページへ遷移するので、そこが灰色の「WA」から緑色の「AC」へ変化すれば正解です!
オレンジ色になる場合、どこか間違えています。じっくりとコードを見直しましょう。
WAは「間違った答えを出力した」、TLEは「コードの実行時間が制限時間(普通2秒)を超えた」、CEは「コードが間違っていて実行までたどり着けなかった」という意味です。
何が楽しいの?
今やったような問題なら、自分でも短時間で計算できるし、あまり楽しくないと思います。
しかし、最初に挙げたこの問題はどうでしょう?
実はこの問題には続きがあります。
これを見ると、言われたとおりに計算しようとすると、最大K個の足し算をしないといけないので、最悪の場合20億回の計算をしないといけません。これは当然手計算ではできませんし、PCでも厳しい量です。
ここで工夫をしてみます。1~Kの和を先に求めておいて、Aに登場した数字の和をそこから引くことにしても、同じ結果になるはずです。
1~Kの和は、$\frac{K(K+1)}{2}$で求められます。これは一回の計算でよいですね。
Aに登場した数字の和を求める、というのは少し大変なのですが、これは最大N回、すなわち20万回の計算でできます。これは手作業では無理な量ですが、PCは賢いので、実は1秒に大体$10^8$回(1億回)くらいの計算ができます。
これで、2秒以内に答えが出せそうだ、と見当がつきます。
このように、うまく工夫をして高速化し正解する、ということに楽しさがあるのではないかと思います。もちろん人によって違うとは思うので、自分の楽しみ方を見つけてください。
さいごに
競プロ、聞いたことはあるしやってみようかな...という人は、ぜひ一度始めてみましょう!
自分に合わないな、と感じたらやめて、やっぱやろうかな、と思ったときに戻ってくるくらいでもいいと思います。
次の記事(未投稿)では、実際にAtCoderのコンテストに参加してレートを上げることについて話したいと思います。