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

関数

関数とは、渡された数に対して特定の処理をするものです。関数はC++で元から用意されているSTLの関数を利用する方法と、関数を自作して使う方法があります。

STLの関数(APG4B 1.14)

STLとは、Standard Template Libraryの略で、C++で用意されている関数のまとまりのことです。
関数名(引数1,引数2,...)という形で呼び出すことができます。

関数	機能
`min(a, b)`	a, b のうち小さい方の値を返す
`max(a, b)`	a, b のうち大きい方の値を返す
`abs(a)`	a の絶対値を返す
`swap(a, b)`	変数 a と変数 b の値を交換する
`sort(vec.begin(), vec.end())`	配列変数 vec の要素を小さい順に並び変える
`reverse(vec.begin(), vec.end())`	配列変数 vec の要素の並びを逆にする

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

int main() {
    int a = -1, b = 2;
    cout << min(a, b) << endl;          // -1
    cout << max(a, b) << endl;          // 2
    cout << abs(a) << endl;             // 1
    cout << a << " " << b << endl;      // -1 2
    swap(a, b);                          
    cout << a << " " << b << endl;      // 2 -1
    
    vector<int> vec = { 3, 2, 5, 1, 4 };
    for (int i = 0; i < 5; i++) {
        cout << vec.at(i) << " ";       // 3 2 5 1 4
    }
    cout << endl;

    sort(vec.begin(), vec.end());
    for (int i = 0; i < 5; i++) {
        cout << vec.at(i) << " ";       // 1 2 3 4 5
    }
    cout << endl;

    reverse(vec.begin(), vec.end());
    for (int i = 0; i < 5; i++) {
        cout << vec.at(i) << " ";       // 5 4 3 2 1
    }
    cout << endl;
}

問題

解答例

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    // 引数が2つと決まっているため max(a, b, c) のような書き方はできません
    int ans = max(a, max(b, c)) - min(a, min(b, c));
    // こういった書き方もできます
    // int ans = max({ a, b, c }) - min({ a, b, c });
    cout << ans << endl;
}

自作関数(APG4B 1.15)

プログラムは上から処理されていくのでmain関数の前に書いてください。
関数の定義は、戻り値の型関数名(引数1,引数2,...) {処理の内容}という形で行えます。
関数の返り値はreturn 返り値という形で指定します。処理の部分に書いてください。
返り値が必要ない場合、戻り値の型はvoidという型にし、return文はreturn;と書いてください。
処理がreturn文に到達した時点で関数の処理は終了します。
引数として関数に渡された値はコピーされて関数に渡されます。なので元の変数が変化することはありません
コピーして関数に渡すことを「値渡し」と言います。
関数に渡された引数を変化させるためには「参照渡し」を行う必要があります。

#include <bits/stdc++.h>
using namespace std;
// 引数として a, b を受け取り、足した結果となるint型の数値を返す関数
int sum(int a, int b) {
    return a + b;
}
// a と b を入れ替える関数
void Swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

int main() {
    int a = 1, b = 2;
    cout << sum(a, b) << endl;          // 3

    cout << a << " " << b << endl;      // 1 2
    Swap(a, b);
    cout << a << " " << b << endl;      // 1 2
}

参照渡し

関数の引数に&をつけることで参照渡しを行うことができます。先に述べたように、参照渡しを行えば関数に渡された引数を変化させることができます。

#include <bits/stdc++.h>
using namespace std;
void Swap(int &a, int &b) { // 参照渡し
    int temp = a;
    a = b;
    b = temp;
}

int main() {
    int a = 1, b = 2;
    cout << a << " " << b << endl;      // 1 2
    Swap(a, b);
    cout << a << " " << b << endl;      // 2 1
}

問題

この問題はすでにある程度書かれているプログラムに追記して完成させる問題です。関数を作らなくても解くことはできますが、使ってみましょう。

解答例

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

int sum(vector<int> scores) {
  int ans = 0;
  for (int i = 0; i < scores.size(); i++) {
    ans += scores.at(i);
  }
  return ans;
}

void output(int sum_a, int sum_b, int sum_c) {
  cout << sum_a * sum_b * sum_c << endl;
}

vector<int> input(int N) {
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  return vec;
}

int main() {
  int N;
  cin >> N;

  vector<int> A = input(N);
  vector<int> B = input(N);
  vector<int> C = input(N);

  int sum_A = sum(A);
  int sum_B = sum(B);
  int sum_C = sum(C);

  output(sum_A, sum_B, sum_C);
}

範囲for文(APG4b 2.01)

範囲for文とは配列の中身1つずつに対して何らかの処理を行う場合に使うことができるfor文の書き方です。
構文は以下のようになっています。

for (配列の要素の型 変数名 : 配列変数) {
    // 各要素に対する処理
}

範囲for文は、変数に配列の中の要素1つをコピーし、その変数に処理を行う、という動作をします。例えば、配列の中身を1ずつ増やして出力したい場合は以下のように書けます。

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

int main() {
    vector<int> vec = { 1, 2, 3, 4, 5 };
    for (int x : vec) {
        x++;
        cout << x << " ";
    }
    // 「2 3 4 5 6」と出力される
}

範囲for文を使わずに書くとこのようになります。

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

int main() {
    vector<int> vec = { 1, 2, 3, 4, 5 };
    for (int i = 0; i < vec.size(); i++) {
        int x = vec.at(i);
        x++;
        cout << x << " ";
    }
}

また、配列だけでなくstring型でも書くことができます。

マクロ

マクロとは、プログラムを機械が読む時(コンパイルする時)に、設定した文字列を自動的に読み替えてくれるようにするものです。
for文など書く量が多く、面倒なものを先に設定しておくことで楽に書くことができます。
例えば以下の文をmain関数の前に書くことでfor文を短く書くことができます。

macro.cpp

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

先ほどの範囲for文のところのコードをマクロを使って書くと以下のようになります。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++) // ここに追加

int main() {
    vector<int> vec = { 1, 2, 3, 4, 5 };
    rep(i, vec.size()) {
        vec.at(i)++;
        cout << vec.at(i) << " ";
    }
}

問題

範囲for文やマクロを使った解き方や使わない解き方など、いろいろと考えてみてください。

範囲for文やマクロなしの解答例

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

int main() {
    vector<int> a(5);
    for (int i = 0; i < 5; i++) {
        cin >> a.at(i);
    }
    for (int i = 0; i < 4; i++) {
        if (a.at(i) == a.at(i + 1)) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

範囲for文を使った解答例

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

int main() {
    vector<int> a(5);
    for (int &x : a) {
        cin >> x;
    }
    for (int i = 0; i < 4; i++) {
        if (a.at(i) == a.at(i+1)) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

マクロを利用した解答例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    vector<int> a(5);
    rep(i, 5) {
        cin >> a.at(i);
    }
    rep(i, 4) {
        if (a.at(i) == a.at(i + 1)) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

多重ループ(APG4b 2.02)

for文やwhile文の中でfor文やwhile文を回すことを多重ループと言います。
処理の順番は、内側のループが終わった後に外側のループが1つ進み、また内側のループが始まるというような順番になっています。

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

int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << "i:" << i << ",j:" << j << endl;
        }
    }
}

上のような2重for文を実行すると下のような結果が得られます。

i:0,j:0
i:0,j:1
i:0,j:2
i:1,j:0
i:1,j:1
i:1,j:2
i:2,j:0
i:2,j:1
i:2,j:2

問題

2重for文を使います。for文の中の変数が被らないように気を付けましょう。

解答例

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

int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p.at(i);
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a.at(i) + p.at(j) == s) {
                count++;
            }
        }
    }
    cout << count << endl;
}

多次元配列(APG4b 2.03)

配列の中の要素一つ一つにさらに配列を入れたものを多次元配列と言います。
2次元配列の場合、vector<vector<変数の型>> 配列名(要素数1,vector<変数の型>(要素数2,初期値));という形で宣言できます。
アクセスはvec.at(i).at(j)という形でできます。
要素数1はvec.size()要素数2はvec.at(i).size()で取得できます。

問題

2次元配列を出力する際、2重for文を使います。

解答例

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);
    for (int i=0; i < m; i++) {
        cin >> a.at(i) >> b.at(i);
    }
    vector<vector<char>> result(n, vector<char>(n, '-'));
    for (int i = 0; i < m; i++) {
        result.at(a.at(i) - 1).at(b.at(i) - 1) = 'o';
        result.at(b.at(i) - 1).at(a.at(i) - 1) = 'x';
    }
    for (int i=0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << result.at(i).at(j);
            if (j != n - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
}