超初心者のための競技プログラミング入門【0: C++を書けるようになる】 #C++

シリーズ目次

この記事について

こんにちは。大学1年のZOIです。高校の後半で競技プログラミングにハマったので、布教用に記事を書きます。

まずこの記事では、競プロをやるために必要なプログラミングの基礎をざっくり説明します。
次の記事では、競プロ自体についての説明をしているので、この記事と次の記事を往復しながら読むとよいかもしれません。

ちなみに、この記事ではプログラミングを全くしたことがない人を対象にして、本当に基礎の部分だけを解説しているので、経験者はさっさと読み飛ばしても全く問題ないです。
まずは、簡単なプログラムを脳内で実行できることを目標にして頑張ってみましょう。

AtCoderで使える言語はいろいろありますが、この記事ではC++を使って説明します。(厳密には、g++のC++20以降)

参考になるサイト・書籍

APG4b: AtCoder公式が作った教材です。この記事よりもいろいろ書いてあるので、APG4bを読めばこの記事はいりません。(存在意義どこ?)
アルゴ式: 競技プログラミングとかアルゴリズムを解説しているサイトですが、ちゃんとプログラミングの基礎も説明してくれます。この記事の上位互換です。(存在意義)
アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門 (鹿本): AtCoderが監修している、競技プログラミングの入門書です。類書の中では最も初心者向けだと思います。この記事の上位互換です。(略)

競プロで使うC++

まず、競プロでC++を使うときは、いつもこんなものを書いている人が多いです。便利なので使うことにします。意味が知りたい人は下の引き出しを読んでください。

#include <bits/stdc++.h>
using namespace std;
int main() {
  // ここに今から書いていく
}

#include <bits/stdc++.h>とは?

これから、vectorやcinなど、いろいろな便利なものを使ってプログラミングをしていきます。
これらは誰かが作ったものですが、その中身はどこか別のファイルに書かれています。
つまり、このファイルの中身をコピペで自分のコードに組み込まなければ、vectorはつかえません。

これを自動化してくれるのが#includeです。
#include <vector>と書けば、自動でvectorに関するファイルの中身をその行の場所にコピペしてくれます。

しかし、vectorを使うときは#include <vector>、cinを使うときは#include <iostream>とするのは多少面倒です。
ここで、bits/stdc++.hというファイルを使います。
このファイルには、用意されているものすべての分の#includeが書かれています。これをincludeすることで、その中身がコピペされ、すべての#includeを書いたような状況になるのです。

もちろん不要なものまで読み込まれるので、業務でのプログラミングでは嫌われますし、競プロでもstdc++.hを使わずに必要なものだけ読み込む人もいます。

(ただし、bits/stdc++.hはgccには組み込まれていますがclangにはありません。気を付けましょう。)

#using namespace std;とは?

これからvectorやcinなどを使ってプログラミングをしていくわけですが、これらは本当はそれぞれstd::vector、std::cinと入力しなければなりません。そこで、この行を書いておけば、このstd::を省略できます。
もちろん欠点もあって、たとえばstd::maxというものがあるのですが、これがmaxとして使えるようになります。
このため、自分でmaxという変数を作ってしまうと、これらが混じって少し面倒なことになります。
そのため、業務では基本使われないし、競プロでもこの行を書かない人もいます。

ちなみにコード中の//はコメントです。これを書いておけば、その行のそれ以降の部分はすべて完全に無視されます。整理用のメモ書きに便利です。

変数

プログラミングでは、処理を並べて書いていくと思っておけばよいです。基本、ある行を実行し終わったら次の行に進む、を繰り返します。
ここで、ある行で使った数や計算した数を記録しておき、もう一度使いたいことがあると思います。
そのようなとき、メモとして使えるのが変数です。

こんな風に書きます。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int a = 0;
  int b = 1;
  // この時点で、aは0、bは1
  a = 3;
  // この時点で、aは3、bは1
}

型

コード中のintとは、変数の型を表しています。
メモ用紙の大きさをイメージしてもらえればよいです。つまり、型によって入る値の範囲や種類が異なります。
よく使う型をいくつか紹介しておきます。

int a = 0; // 整数。±10^9くらいは入る。それを超えるとバグる。
long long b = 0; // 整数。±10^18くらいまでは入る。
string s = "Hello World"; // 文字列。0文字～(ほぼ)無限文字。ダブルクオーテーション(")で囲んでから代入。
char c = 'a'; // 一文字。シングルクオーテーションで囲んでから代入。
bool x = true; // 〇か×か。trueは〇、falseは×。後述するifなどの()の中に変数を入れると、条件式の代わりになる。

ただし、先ほどのサンプルを見ればわかるように、型を明記するのは最初の1回だけです。
1回目だけ、変数の作成と書き込み(代入)を同時にしているのです。
ちなみに、作成だけして書き込みをしないこともできます。この時の中身は不定です。使う前にはちゃんと中身を入れましょう。

四則演算

int a=0;
a = a + 1;
// このときaは1

四則演算として、+、-、*、/があります。ついでに、a/bのあまりはa%bです。
当然ですが、この左右は数字でなければなりません。つまり、stringとstringの掛け算とかはないです。(作ればありますが)

ちなみに、a = a + bは面倒なのでa += bと書けます。また特別に、a += 1はa++または++aと書けます。(厳密にはこの2つは少し違うけど)
他の演算も同様です。

分岐・ループ

先ほど、基本的には上から下へ実行されると書きました。まずはこれの例外を紹介します。

if

条件です。ある条件を満たすときのみ実行するコードを作れます。
「aとbが等しいなら」はa == bです。イコールは2つです。
大小比較は<、<=、>、>=です。

int a = ???;
int b = ???;
if(a == 0) {
  // aが0のときのみ、この{}の間は実行される
} else if(b == 1) {
  // aが0でないとき、もしbが1であれば、この{}の間は実行される
} else {
  // 以上のどれにも当てはまらなかったとき、この{}の間は実行される
}

ifの()の中身はbool型です。また、bool型なら()に入れられます。
何を言っているかわかりにくいので、例を見たほうが速いです。つまり、こんなこともできるということです。

if(true) {
  // 絶対実行される
}
if(false) {
  // 絶対実行されない
}

// 条件を外に出す
bool b = a<=3;
if(b) {
  // ...
}

for

基本的に、ある回数の繰り返しに使われます。

for(int i=0; i<10; i++) {
  // ここは10回実行される
  for(int j=0; j<5; j++) {
    // 「5回実行される」が10回実行されるので、つまりこの行は50回実行される
  }
}

この、for(int i=0; i<N; i++)をまず覚えましょう。これでN回の繰り返しができます。

詳しく

forの()の中は、;2つで3つに分かれています。それぞれ第一要素、第二要素、第三要素とします。
第一要素は、初めてfor文に差し掛かった時に実行されます。今回の場合、変数を定義しています。この変数は、forの内部(()と{}内部)でしか使えないようになります。
第二要素は、実行するかどうかの判断基準(bool)です。成立するなら実行します。今回は、iの範囲が条件です。
第三要素は、{}の実行が終わるごとに行う処理です。

つまり、「forにたどり着いた」→「int型の整数iを定義・0を代入」→「i<10か? (はい)」→「{}を実行」→「i++」→「i<10か? (はい)」→...→「i<10か? (いいえ)」→「for脱出、次の行へ」となります。
for内から見れば、i=0,1,2,3,...,9の10回が実行されます。

while

forよりシンプルなループです。条件を満たす間、ずっとループが続きます。
これは、さっきのforと同じような動作になります。

int i=0;
while(i<10) {
  // いろいろな処理
  i++;
}

入出力

AtCoderでは、様々な条件が与えられるので、それを受け取らなければいけません。
数字N、M、文字列Sがこの順番で与えられるとすれば、以下のように受け取れます。

int N, M; // 省略してこう書くこともできる、中身は不明
string S;
cin >> N >> M >> S;

>>で、入力される順に受け取ればよいです。
逆に、出力はこうです。

int N, M; // 中身は入れてあるとする
string S; // 中身は入れてあるとする
cout << N << endl << M << endl << S << endl;

endlを送ると改行してくれます。これがなければ、単に出力するだけなので、N=2、M=4のとき24と出力されます。
基本、AtCoderでは回答の最後は改行しておきましょう。

配列

例えば、「箱がN個あります。それぞれの重さを教えます。」みたいな問題の時は、N個の変数を作りたくなります。
これを実現するのが配列です。

C++には普通の配列(生配列と呼ばれる)もあるのですが、使いにくいので、機能が追加されたvectorを使う人が多いです。

vector<int> box_w(N, 0);
for(int i=0; i<N; i++) {
  cin >> box_w[i];
}

vector<???>の???の部分に型を書くことで、その型の変数をたくさん作ってくれます。
変数の後に()がついていますが、その中身の一つ目が要素数、二つ目が初期値です。
int ????=0;をN回やってくれるわけです。

また、配列vのi番目はv[i]です。ただし、このiは0スタートです。
つまり、我々が日常で「1番目」と呼ぶ先頭は、配列としてはv[0]です。とても引っ掛かりやすいので気を付けましょう。

ここまでわかれば、上のコードではN個の入力を受け取り配列に格納している、とわかると思います。

さいごに

かなり簡単な説明で終わってしまったので、わかりにくいところがあればコメントやTwitterで教えてください。

これでプログラムが最低限読めるようになったはずです。あとは慣れです。ゆっくりとでよいので、読んだり書いたりしていればスピードも正確性も上がっていきます。

次の記事では、競技プログラミングとは何をするものなのか、について説明します。