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

イテレータとは

構造体の要素を参照、移動、変更などができる便利なもの！
vector型で使ったA[i]（添え字）とは少し違って、A[i]が配列の要素を参照するのに対して、イテレータは直接的には要素を指していない。
イテレータの例として、sortやreverseで使うbegin()、end()がある。
イテレータを変数に入れる場合はautoを用いる。
イテレータもしくは、イテレータを値として持つ変数の頭に*を付けるとその要素を取得できる。

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

int main() {
    vector<int> A = { 1, 2, 3, 4, 5 };

    auto itr = A.begin();
    cout << *itr << endl;  // 1

    // インクリメントして次の要素を参照
    itr++;
    cout << *itr << endl;  // 2

    // A[2]と同じ使い方もできる
    cout << *(A.begin() + 2) << endl;  // 3

    // A.end()は配列の最後の要素の "次" を示す
    itr = A.end();

    // デクリメントして最後の要素を参照させる
    itr--;
    cout << *itr << endl;  // 5
}

問題

添え字は使わないで、イテレータを用いて問題を解いてみよう！

iterator.cpp

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

int main() {
    vector<int> a(10);
    for (int i = 0; i < 10; i++) {
        // (1)
    }

    int num = 0;                // numは、画面に表示される数字
    auto itr = a.begin();       // itrは、ボタンを押して変わった後の要素のイテレータ
    for (int i = 0; i < 3; i++) {
        // (2)
        // (3)
    }

    // (4)

    return 0;
}

ヒント

*(a.begin()+i) と a[i] は同じ
for文の中で、numとitrをボタンを押したごとに変化させよう

解答例

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

int main() {
    vector<int> a(10);
    for (int i = 0; i < 10; i++) {
        cin >> *(a.begin() + i);
    }

    int num = 0;                // numは画面に表示される数字
    auto itr = a.begin();       // itrはボタンを押したとき変わる要素のイテレータ
    for (int i = 0; i < 3; i++) {
        itr = a.begin() + num;
        num = *itr;
    }

    cout << num << endl;

    return 0;
}

別解：添え字を使った場合

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

int main() {
    vector<int> a(10);
    for (int i = 0; i < 10; i++) {
        cin >> a[i];
    }

    int num = 0;                // numは画面に表示される数字
    for (int i = 0; i < 3; i++) {
        num = a[num];
    }

    cout << num << endl;

    return 0;
}

他の構造体での活用例

配列のように要素同士が連続していない構造体に対しても使える性質を持つ。
setなどの他の構造体にはA[i]の形でアクセスできないものがある。
mapは、map<Keyの型, Valueの型> 変数名; で宣言できる。(mapなど他の構造体は今後詳しくやります)

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

int main() {
    map<int, int> mp;
    mp[50] = 3;
    mp[1] = 5;
    mp[12000] = 1;

    // mapのイテレータは、mapのKeyの昇順に移動する
    auto map_itr = mp.begin();
    cout << map_itr->first << endl;  // 1 (一番小さいキーが1のため)
    map_itr++;
    cout << map_itr->first << endl;  // 50
    // map_itr += 2 とすることはできなくて、mapのイテレータは1ずつしか足せない
}

　イテレータを使う関数

イテレータを用いると処理を一般化できることが多く、STLにおいて「一連の要素に対して何かを行う」ような関数はイテレータを引数に取る形で実装されている。

関数	機能
`sort(A.begin(), A.end())`	配列Aの要素を昇順に並び替える
`reverse(A.begin(), A.end())`	配列Aの要素を逆にする
`min_element(A.begin(), A.end())`	配列Aの要素の最小値のイテレータを求める
`max_element(A.begin(), A.end())`	配列Aの要素の最大値のイテレータを求める
`accumulate(A.begin(), A.end(), x)`	配列Aの総和を求める

int型の配列の場合以下のように使えます。

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

//配列の中身を出力する関数
void print(vector<int> vec) {
    for (int now : vec) cout << now << ' ';
    cout << endl;
    return;
}

int main() {
    vector<int> A = { 4, 5, 1, 3, 2 };
    print(A);                      // 4 5 1 3 2
    
    // sortの場合
    sort(A.begin(), A.end());
    print(A);                      // 1 2 3 4 5

    // reverseの場合
    reverse(A.begin(), A.end());
    print(A);                      // 5 4 3 2 1

    // min_elementの場合
    auto min_itr = min_element(A.begin(), A.end());
    cout << *min_itr << endl;      // 1

    // max_elementの場合
    auto max_itr = max_element(A.begin(), A.end());
    cout << *max_itr << endl;      // 5

    // accumulateの場合
    // 第 3 引数に0を入れるとint型になってしまうので、小数や long long 型を扱うときは注意
    int sum = accumulate(A.begin(), A.end(), 0);
    cout << sum << endl;           // 15

    return 0;
}

sortやreverseは同様にstring型でも使うことが出来ます。

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

int main() {
    // 要素がstring型の配列の場合
    vector<string> str = { "apple", "dog", "student", "sun", "game" }; 

    sort(str.begin(), str.end());
    for (string i : str) cout << i << ' ' ;     // apple dog game student sun
    cout << endl;

    reverse(str.begin(), str.end());
    for (string i : str) cout << i << ' ' ;      // sun student game dog apple
    cout << endl;

    // 文字列の場合
    string s = "maximum";

    sort(s.begin(), s.end());
    cout << s << endl;       // aimmmux

    reverse(s.begin(), s.end());
    cout << s << endl;       // xummmia

    // 大文字、小文字、数字、記号が混ざる場合
    string t = "Oh11ne-Y0ro4ku";

    sort(t.begin(), t.end());  // ASCIIコード表を参照
    cout << t << endl;       // -0114OYehknoru

    reverse(t.begin(), t.end());
    cout << t << endl;       // uronkheYO4110-
}

練習問題

今回紹介した関数を使って問題を解いてみよう！！

1 : A - Tiny Arithmetic Sequence

practice_1.cpp

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

int main() {
    vector<int> a(3);
    for (int i = 0; i < 3; i++) cin >> a[i];

    // これより下に記述

    return 0;
}

ヒント

sortを使おう
if文を使って条件に合うか確かめよう

解答例

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

int main() {
    vector<int> a(3);
    for (int i = 0; i < 3; i++) cin >> a[i];

    sort(a.begin(), a.end());

    if (a[2] - a[1] == a[1] - a[0]) 
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

2 : A - 321-like Checker

practice_2.cpp

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

int main() {
    int n;
    cin >> n;
    vector<int> d; // nを各桁に分解して配列として保存する

    // nが0より大きい時繰り返す
    while (n > 0) {
        // (1)
        // (2)
    }

    // (3)

    for (/* (4) */) {
        if (/* (5) */) {
            // (6) 二行
        }
    }

    // (7)

    return 0;
}

ヒント

while文の中で、配列dにnを10で割った余りを追加し、nを10で割ろう
reverseを使って、元の順番に戻そう
配列外参照に気を付けながら、配列dの前後を見比べよう

解答例

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

int main() {
    int n;
    cin >> n;
    vector<int> d; // nを各桁に分解して配列として保存する

    // nが0より大きい時繰り返す
    while (n > 0) {
        d.push_back(n%10); // dの末尾にnを10で割った余りを追加
        n /= 10; // nを10で割る
    }

    // この時、dにはnを右から見たときの順に入っている。つまり逆
    // 例) n = 321 の時、 d = { 1, 2, 3 }
    reverse(d.begin(), d.end());

    for (int i = 1; i < d.size(); i++) {
        // dの前後を見比べて条件に合うか確かめる
        if (d[i-1] <= d[i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    
    return 0;
}

別解

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

// nをstring型で受け取ると簡単に求めることが出来る
int main() {
    string n;
    cin >> n;
    for (int i = 1; i < n.size(); i++) {
        if (n[i-1] <= n[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

3 : A - ABC Preparation

practice_3.cpp

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

int main() {
    vector<int> a(4);
    for (int i = 0; i < 4; i++) cin >> a[i];

    // これより下に記述

    return 0;
}

ヒント

min_elementを使おう
min_elementはイテレータを取得することに注意して解こう
minを使ったり、forとifを組み合わせたりして解くこともできるよ

解答例

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

int main() {
    vector<int> a(4);
    for (int i = 0; i < 4; i++) cin >> a[i];

    int min_num = *min_element(a.begin(), a.end()); //min_elementはイテレータを取得することに注意

    /*
    別解1:
    int min_num = min({ a[0], a[1], a[2], a[3] });
    */

    /*
    別解2:
    int min_num = 100;
    for (int i = 0; i < a.size(); i++)
        if(min_num > a[i])
            min_num = a[i];
    */

    cout << min_num << endl;

    return 0;
}

ラムダ式ソート

そもそもラムダ式ってなに？？

関数オブジェクトを簡易的に定義するための機能
プログラム中の様々なタイミングで定義が可能
ラムダ式による関数オブジェクトは[](引数){処理}形式で定義し、autoで保持することができる。

関数オブジェクトは、関数のように振る舞うことのできるオブジェクトのこと。関数オブジェクトは多くの場合、クラスに対して関数呼び出し演算子を定義することで実現される。C++ではoperator()メンバ関数のオーバロードによってそれを実現する。

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

int main() {
    auto f = []() {
        cout << "Hello, world!" << endl;
    };

    f(); // Hello, world!
}

上の例では、ラムダ式[]() {...}で作成した関数オブジェクトを変数fに代入しています。

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

int main() {
    auto fn = [](int v) { return v * 2; };
    fn(3); // 6
}

上の例では、引数としてintを1つ受け取っています。

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

int main() {
    auto f = [](int i, int j) -> int {
        return i * j;
    };

    cout << f(2, 3) << endl; // 6
}

戻り値は->で指定します。上の例ではint型の戻り値を返す関数オブジェクトを指定しています。

ラムダ式ソートの使用例

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

int main() {
    vector<int> vec = { 3, 1, -5, -2, 4 };

    // 昇順にソート
    sort(vec.begin(), vec.end());
    for (int v : vec) cout << v << ' '; // -5 -2 1 3 4
    cout << endl;

    // 絶対値の小さい順にソート
    sort(vec.begin(), vec.end(), [](int i, int j) -> bool {
        return abs(i) < abs(j); // absは引数の絶対値を返す関数
    });
    for (int v : vec) cout << v << ' '; // 1 -2 3 4 -5
    cout << endl;

    return 0;
}

ラムダ式による比較関数をオプションで渡すことによって、既定の比較方法以外でも並べ替えを行うことが出来ます。

問題集

時間があるときに、挑戦してみてください。

基礎

少し難しい問題も混じってます。

発展

難しいです。ラムダ式ソートを練習したいときに見てみてください。