C++ 競プロ講座 ② 制御構文・vector
0. 競プロ用テンプレート
#include<bits/stdc++.h>
using namespace std;
int main() {
// ここに書く
return 0;
}
#include <bits/stdc++.h>… 標準ライブラリを全部まとめて読み込むusing namespace std;…std::を省略できる- 入出力は
cin >> x;/cout << x << endl;
1. if-else / for / while(復習・差分のみ)
if-else
int x;
cin >> x;
if (x > 0) {
cout << "正数" << endl;;
} else if (x == 0) {
cout << "0" << endl;
} else {
cout << "負数" << endl;
}
- Javaと同じです. ()で条件式を書いて, {}で条件が満たされたときに動作するという形です.
for
for (int i = 0; i < n; i++) {
cout << i << "\n";
}
- Javaと同じです. for (<forに入る前の初期化>;<forを継続する条件>;<forの処理一回ごとに行う処理>)
- C++ にも拡張 for(範囲 for)が存在, Java の
for (int v : arr)と同等- 競技プログラミング的には,
auto(変数の型)
- 競技プログラミング的には,
vector<int> a = {1, 2, 3};
for (auto v : a) {
cout << v << endl;
}
while
int n;
cin >> n;
while (n > 0) {
cout << n % 2;
n /= 2;
}
do-while,break,continueも Java と同じです.
2. vector(本日のメイン)
- 何者？
Java の ArrayList に相当する可変長配列. 競技プログラミングだと(少なくとも私の場合は)普通の配列は使いません.
- そもそも配列って？
複数の変数を1つの変数にまとめて管理できる機能です. 例えば,
int a1 = 10;
int a2 = 5;
int a3 = 19;
int a4 = -10;
int a5 = 23;
なんてやってもいいですが, 気まずいですよね？
これをまとめてあげましょう！！！という機能です.
普通の配列は以下のように書きます.
int a[] = {10, 5, 19, -10, 23};
じゃあその要素にアクセスするにはどうするの？っていうと下記の感じです.
cout << a[0] << endl; // 1番目の要素
cout << a[4] << endl; // 5番目の要素
0から始まり, 配列のサイズ- - が最終要素なのに注意してください.
- じゃあ可変長配列って？
長さをプログラム動作時に動的に変更できる配列です. 例えば,
- 配列の長さを5でとったけど, 後から値を追加したーい
- int nで長さ用の変数を宣言して, cinで値を受け取った後に配列を宣言したーい
なんてやろうとすると普通の配列ではできないんですね. じゃあどうにかしよう()(ついでにいろんな関数を足したろ！！！)という感じです.
宣言・初期化
vector<int> a; // 空
vector<int> b(5); // 要素5個、全部0
vector<int> c(5, 7); // 要素5個、全部7
vector<int> d = {1, 2, 3}; // 初期値あり
vector<vector<int>> grid(h, vector<int>(w, 0)); // 2次元 h×w を0で初期化
こんな感じで宣言できます.
vector<<型名>> <配列の変数名>(<配列の長さ>, <初期化変数>); # 1次元配列
vector<vector<<型名>>> <配列の変数名>(<配列の長さ(1次)>, (vector<型名>, <配列の長さ(2次)>);
基本操作
a.push_back(10); // 末尾に追加
a.emplace_back(20); // 末尾に追加(基本こっちでOK)
a.pop_back(); // 末尾を削除
a.size(); // 要素数
a.empty(); // 空かどうか
a[i]; // i番目アクセス(範囲チェックなし)
a.front(); // 先頭
a.back(); // 末尾
a.clear(); // 全削除
サイズ変更
a.resize(10); // 要素数を10に(増えた分は0)
a.assign(5, 3); // 要素数5、全部3に作り直す
よく使うアルゴリズム関数
<algorithm> というライブラリの実装関数です. 競技プログラミングだとよく使います.
vector<int> a = {3, 1, 4, 1, 5};
sort(a.begin(), a.end()); // 昇順ソート -> 1 1 3 4 5
sort(a.rbegin(), a.rend()); // 降順ソート -> 5 4 3 1 1
reverse(a.begin(), a.end()); // 逆順
実際に動かすゾーン
#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];
}
// 整列させたい
sort(a.begin(), a.end());
// 昇順にソート
for (auto x : a)
{
cout << x << ' ';
}
cout << endl;
// 降順にソート
sort(a.rbegin(), a.rend());
for (auto x : a)
{
cout << x << ' ';
}
cout << endl;
// 値を適当に追加する
a.push_back(1000);
// そのまま出力する
for (auto x : a)
{
cout << x << ' ';
}
cout << endl;
// 値をソート
sort(a.begin(), a.end());
for (auto x : a)
{
cout << x << ' ';
}
cout << endl;
// 末尾の値を消去する
a.pop_back();
for (auto x : a)
{
cout << x << ' ';
}
cout << endl;
}
練習問題
https://atcoder.jp/contests/abc328/tasks/abc328_a
https://atcoder.jp/contests/abc330/tasks/abc330_a