【第1回】はじめての競技プログラミング

今回から、競技プログラミングの基礎を学んでいきます。 APG4b(https://atcoder.jp/contests/apg4b)に沿って講義を行うので、理解が進んでいる方はAPG4bを進めてもらって構いません。

プログラムの基本

基本中の基本

C++のプログラムはすべてmain関数内の上から下に順番に実行されます。

コードはmain関数の中({ と } の間)に処理を書いてください。

命令一つ一つを「文」と呼びます。文の最後にはかならずセミコロン ; を付けましょう。 (Pythonでは改行するだけでOK)

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << "Hello World!" << endl;
}

入力・出力

データを入力する為にはcin(シーイン)を使います。
cin >> a; で整数が 1 つだけ入力されます。cin >> a >> b;とすると、この場合は 2 つの整数がそれぞれ変数 a, b に格納されます
データを表示(出力)するには、cout(シーアウト)を使います。文字列を扱うには" "で囲いましょう。改行するときはendl(エンドエル)と書きましょう。

※cinの時は>>、coutのときは<<であることに注意してください。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;  // aとbに例えば3と5が入力されると
    cout << a + b << endl;  // 8と出力される
}

長いプログラムを書いていると、何でこう書いたのか分からなくなってしまうときがあります。でもパソコンに付箋を貼るわけにもいかないし、そのままコードの中にメモを書いてしまうとプログラムが動かなくなってしまいますね。

そんなときには//と書くことで、その後ろに続く文字がプログラムに影響しない「コメント」になります。

デバッグ作業を行うときなど、一時的にこのコードを実行しないようにするときにも//は有効です。(「コメントアウト」といいます。)

変数・型

変数

変数とは、一度使ったデータを後で使いたいときのために名前をつけておくメモのようなものです。変数名は基本的に自由ですが、以下のものは名前に使うことができません。

数字で始まる名前
アルファベットや数字、_(アンダースコア)以外が使われている名前
予約語(using, int, namespace などのC++で使われている一部の単語)

また同じ名前の変数も宣言できません。

型

型	扱えるもの
`int`	約 $10^9$ までの整数を扱える ( $-2^{31} \sim 2^{31}-1$ まで OK)
`long long`	約 $10^{18}$ までの整数を扱える ( $-2^{63} \sim 2^{63}-1$ まで OK)
`double`	約 $\pm 1.7 \times 10^{308}$ までの実数を扱える
`string`	文字列

intとlong longの違いは、扱える範囲の広さです。
これらは、表せる値の範囲を超えるとオーバーフローします。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 2147483647; // int型の最大値
    cout << a << endl; // int型で扱える範囲内の為、オーバーフローは起こらない
    cout << a + 1 << endl; // オーバーフローが起こる
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long b = 2147483647;
    cout << b + 1 << endl; // long long型はint型より扱える範囲が広いため、オーバーフローは起こらない

    b = 9223372036854775807; // long long型の最大値
    cout << b + 1 << endl; // オーバーフローが起こる
}

変数の宣言の仕方

変数は<データの型>　<変数名>;と記述して宣言します。
,(カンマ) で区切ると、複数の変数を宣言することもできます。(変数が同じ型の場合のみ)
変数宣言後の、最初の値の代入を初期化といいます。
初期化のタイミングは、変数宣言時と代入時のどちらでも構いません。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;  // int型の変数を宣言
    a = 3;  // 変数aを初期化
    b = 5;  // 変数bを初期化
    int c, d = 8;  // 宣言と同時に初期化もできる(この場合、初期化されるのはdのみ)
    b = 10;  // bの値を10に変更
    cout << a + b + d << endl;  // 21と出力される
    cout << c << endl;  // cは初期化してないので、何が出力されるかはわからない
}

四則演算

商を求めるとき、intやlong longだと小数点以下切り捨てになることに注意してください。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 1, b = 2;
    cout << a + b << endl;  // 和 3
    cout << a - b << endl;  // 差 -1
    cout << a * b << endl;  // 積 2
    cout << a / b << endl;  // 商 0 (a, bはint型なので、小数点以下は切り捨てられる)
    cout << a % b << endl;  // 剰余 1
}

プログラミングの基本的な流れ

変数を宣言する
変数に数値を代入(初期化)する(または cin する)
変数に手を加えていく(四則演算など)
答えを出力する(cout する)

ここで問題を解いてみましょう。

PracticeA - Welcome to AtCoder

問題

整数 $a, b, c$ と文字列 $s$ が与えられるので、 $a + b + c$ と $s$ を並べて出力しなさい。

制約

$1 \le a, b, c \le 100$
$1 \le |s| \le 100$

解答例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c;  // 変数宣言
    string s;  // 変数宣言
    cin >> a >> b >> c >> s;  // 入力
    cout << a + b + c << " " << s << endl; //四則演算、出力
}

類題

if文・論理演算子

if 文

	意味
`if`文	条件が正しかった時だけ実行される
`else`句	条件が正しくなかった時実行される

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a;
    cin >> a;
       if (a > 0) {
        // a > 0 のときに実行される
        cout << "aは正の数です" << endl;
    } else if (a < 0) {
        // a > 0 ではなく、かつ a < 0 のときに実行される
        cout << "aは負の数です" << endl;
    } else {
        // a > 0 でも a < 0 でもないときに実行される
        cout << "aは0です" << endl;
    }
}

if文の条件式は、bool型の値を返す式でなければなりません。

比較演算子

!=, <=, >= は全部 = が右にあります

演算子	意味
`x == y`	x, y は等しい
`x != y`	x, y は等しくない
`x > y`	x は y より大きい
`x < y`	x は y より小さい
`x >= y`	x は y 以上
`x <= y`	x は y 以下

論理演算子

演算子	意味	真になるとき
`!`(条件式)	否定	条件式が偽
(条件式 1) `&&` (条件式 2)	かつ	条件式 1 と条件式 2 がともに真
(条件式 1) `\|\|` (条件式 2)	または	条件式 1 と条件式 2 のどちらかが真

例

`x`	`y`	`!x`	`x && y`	`x \|\| y`
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

以上のことが分かれば、B 問題を解くことができます。

ABC086A - Product

問題

$a, b$ の積が偶数か奇数かを判定するプログラムを書いてください。

制約

$1 \le a,b \le 100$
$a,b$ は整数

ヒント

a,b の積を 2 で割った余りが 0 なら偶数、1 なら奇数であることを利用
文字列を出力するときは、"(ダブルクオーテーション)で囲む

解答例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b;
    c = a * b;
    if (c % 2 == 0) {  // cを2で割った余りが0なら偶数
        cout << "Even" << endl;
    } else {
        cout << "Odd" << endl;
    }
}

文字列・文字・複合代入演算子

文字列(string)の扱い方

string型(文字列)の変数sに対して、以下のような処理ができます:

処理	記法
文字列の長さの取得	`s.size()`
文字列の取得	`s.at(i)` または `s[i]`

添え字は 0 から数え始めることに注意してください！

1 文字目 → s[0]
2 文字目 → s[1]
n 文字目 → s[n - 1]

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "abcde", t = "fghij";
    cout << s.size() << endl;  // 5
    cout << s[0] << " " << s.at(0) << endl;  // a a  (どちらもaが出力される)
    s = s + t;  // sにtを連結
    cout << s << endl;  // abcdefghij　
}

文字(char)の扱い方

char型は 1 文字だけを表す型です。
文字列は"(ダブルクオーテーション)で囲みますが、文字は'(シングルクオーテーション)で囲んで表現します。

#include <bits/stdc++.h>
using namespace std;

int main() {
    char c = 'a'; // "a" ではない
    cout << c << endl;  // a
}

複合代入演算子

演算子	意味
`x += y`	`x = x + y`
`x -= y`	`x = x - y`
`x *= y`	`x = x * y`
`x /= y`	`x = x / y`
`x %= y`	`x = x % y`
`x++`	`x = x + 1`
`x--`	`x = x - 1`
`++x`	`x = x + 1`
`--x`	`x = x - 1`

x++は「後置インクリメント」、x--は「後置デクリメント」といい、xの現在の値を評価してから1を加えたり減らしたりします。
++xは「前置インクリメント」、--xは「前置デクリメント」といい、xに1を加えたり減らしたりしてから値を評価します。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 5;
    int a = x++; // aには5が代入され、その後xが6になる
    int b = ++x; // xが先に7になり、それがbに代入される
}

以上のことが分かれば、問題を解くことができます。

ABC081A - Placing Marbles

問題

文字列 $s$ のうち、1 の個数を出力してください。

制約

$s$ は 3 文字の文字列で、'1' または '0'のみからなる

解答例

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = 0;
    if (s[0] == '1') ans += 1;  // ans++;でもいい
    if (s[1] == '1') ans += 1;
    if (s[2] == '1') ans += 1;
    cout << ans << endl;
}

ループ・配列

for 文

for文は、繰り返し処理を行うための文です。

for (初期化式; 条件式; 変化式){
    //繰り返し処理
}

continueを使うと次のループに移行することができます。
breakを使うと今いるループを抜けることができます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    for(int i = 0; i < 3; i++) {  // iが3未満の間繰り返す
        cout << "hello" << i << endl;
        if (i == 1) break;  // iが1になったらfor文を抜ける
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 0; i < 3; i++) {  // iが3未満の間繰り返す
        if (i == 1) continue;  // iが1になったら以降の処理をスキップして次の繰り返しに移る
        cout << "hello " << i << endl;
    }
}

while 文

while文は、条件式がtrueの間、繰り返し処理を行うための文です。

while (条件式) {
    //繰り返し処理
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int i = 0;
    while (i < 3) {  // iが3未満の間繰り返す
        cout << "hello world " << i << endl;
        i++;  // iを1増やす
    }
}

配列

配列は、同じ型の変数を複数まとめて扱うためのデータ構造です。C++ではvector型を用いて表現される事が多いです。

vector配列はvector<型名> n(要素数, 初期値);とすることで宣言できます。

配列は要素を指定しないとすべての要素が0で初期化されます。

vector配列vec(ここの名前は自由につけてもらって大丈夫です)に対して、以下のような操作ができます:

配列の操作	記法
配列の要素数を取得する	`vec.size()`
配列の要素を取得する	`vec.at(i)` または `vec[i]`
配列の末尾に要素を追加する	`vec.push_back(x)`
配列の末尾の要素を削除する	`vec.pop_back()`

for 文を使って配列を走査する

#include <bits/stdc++.h>
using namespace std;

int main()　{
    vector<int> vec;  // int型の配列vecを宣言
    vec = {1,2,3,4,5};  // 配列に値を代入
    cout << vec[0] << endl;  // 配列の0番目の要素を出力
    cout << vec.size() << endl;  // 配列の要素数を出力

    vector<long long> vec2(5, -1);  // 要素数5のlong long型の配列vec2を宣言して、すべての要素を-1で初期化
    for (int i = 0; i < 5; i++) cin >> vec2[i];  // 配列の要素を入力

    vec2.push_back(6);  // 配列の末尾に6を追加
    cout << vec2[5] << endl;  // 6 (配列の末尾の要素を出力)
}

これで、問題を解くことができます。

ABC081B Shift only

問題

$N$ 個の正の整数 $a_1, a_2, ..., a_N$ が与えられます。これらの整数がすべて偶数なら、それぞれ 2 で割ったものに置き換えます。このとき、操作を行った回数の最小値を求めてください。

制約

$1 \le N \le 200$
$1 \le a_i \le 10^9$

解答例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];  // 配列の要素を入力

    int ans = 0;  // 操作を行った回数
    while (true) {  // 無限ループ
        for (int i = 0; i < n; i++) {  // 配列の要素を走査
            if (a[i] % 2 == 1) {  // 奇数の場合  a[i]%2!=0でもいい
                cout << ans << endl;  // 操作を行った回数を出力
                return 0;  // main関数を抜ける
            }
            a[i] /= 2;   // 偶数の場合、2で割る
        }
        ans++;   // 操作を行った回数を1増やす
    }
}

練習問題

まとめ

今回で APG4b の第 1 章の内容は大体終わりました。練習問題もあるので解いてみてください。一回やっただけでは理解できないと思うので、何度もやってみてください。