C++ における vector の使い方
一昨日は ABC121 がありました。宣言した通り、ABCの結果と、問題を解くのに使えそうな C++ のライブラリについての記事を書こうと思います。今回はC++におけるvector についてです。AtCoder のコンテストに提出されている C++ のコードを読むと、配列ではなく vector を使っているものがたくさんあります。何故 vector の方が好まれているのか、ずっと気になっていました。今回は、vector の使い方について、私なりにまとめていきたいと思います。
ABC121の結果
まずは、ABC121 の結果についてです。
今回、初の全完を達成しました。かなり嬉しかったです。しかし、D 問題については4回も WA を出してしまいました。原因は初歩的なコーディングミスでした。更にレートを上げるために、こういうミスには、すぐ気づけるようになりたいですね。以前よりも、コーディングのスピードは上がったと思います。これからも精進を続けたいと思います。コーディングの速さと、アルゴリズムの知識、両方がもとめられるのが面白いところですね。言語に関する記事をだけでなく、アルゴリズムに関する記事も、いつか書きたいと思っています。
ABC121 の B 問題と C 問題は、配列か vector を使って解くのが一般的だと思います。コンテスト中は、使い慣れている配列を使って解きました。この問題を解く、vector を使ったコードを書くことを目標にして、vector について調べてみました。
vectorの基本
色々なサイトが参考になりそうでしたが、次のサイトが一番参考になりそうでした。
vivi.dyndns.org
vector は、要素の数を、後から増やすことができる配列のようなものです。まずは宣言の仕方と、基本的な使い方を見てみます。
- C++の標準ライブラリであり、vector というヘッダーファイルを、インクルードすることで使うことができる(#include <vector> とコードの始めに書くことで使える)
- vector の宣言は std::vector<"格納したい変数の型"> "名前";で行う (name space std; と書くことで std は省略できる)
- std::vector<"格納したい変数の型"> "名前"(n); で要素数 n の vector を宣言できる
- A という vector の i 番目の要素には A[i] でアクセスでき、代入もできる
- size メソッドを使って要素数を取得できる
- push_back メソッドを使って末尾に要素を追加できる
試しに使ってみます。
#include <iostream> #include <vector> using namespace std; int main(){ vector<int> A(3); // 要素数3の vector の宣言 A[0] = 4; // A[0]に4を代入 A[1] = 2; // A[1]に2を代入 A[2] = 7; // A[2]に7を代入 cout << "現在の要素は" << endl; // 現在の要素を出力 for(int i=0;i < (int)A.size();i++){ cout << A[i] << " "; } cout << endl; A.push_back(5); // 末尾に5を追加 A.push_back(1); // 末尾に1を追加 cout << "現在の要素は" << endl; // 現在の要素を出力 for(int i=0;i < (int)A.size();i++){ cout << A[i] << " "; } cout << endl; }
実行結果は以下のようになります。
現在の要素は 4 2 7 現在の要素は 4 2 7 5 1
B 問題
まず ABC121 の B 問題で vector を使ってみます。
atcoder.jp
B 問題では次のことが便利です。
二次元の vector は int の vector を要素にもつ vector ということです。今回はこれを使って B 問題を解くことにしました。解答のコードは以下のものです。
#include <iostream> #include <vector> using namespace std; int main(){ int N, M, C; cin >> N >> M >> C; vector<int> B(M); vector<vector<int>> A; for(int i=0;i<M;i++){ cin >>B[i]; } for(int i = 0;i<N;i++){ vector<int> IN(M); for(int j=0;j<M;j++){ cin >> IN[j]; } A.push_back(IN); } int count = 0; for(int i=0;i<N;i++){ int sum = 0; for(int j=0;j<M;j++){ sum += A[i][j] * B[j]; } sum += C; if(sum > 0) count++; } cout << count << endl; }
まず整数 と
を、標準入力から受け取ります。その後、
を格納する vector を用意します。今回は要素数が
と分かっているので、サイズを指定して宣言しました。その後順番に、各B[0], B[2], ..., B[M-1] に、標準入力から受けとった値を格納していきます。問題は
を満たす全ての
について、
を入力から受け取る部分です。今回は、次の操作を行うことで実装しました。
- int 型の二次元 vector A を宣言する
- int 型の変数 i = 0 を宣言する
- 要素数
の vector IN を用意する
- IN[0], IN[1], ..., IN[M-1] に標準入力から受け取った値、すなわち
を格納する
- A.push_back(IN) でvector IN を A の末尾に追加する
- i++ を行い、i <
これは、 A が vector<int> を要素に持つ vector であることを利用しています。作った vector を push_back で末尾に追加することで、正しい順序の二次元 vector を作ることができます。
C 問題
次は C 問題についてです。
atcoder.jp
C 問題は pair を使った実装が簡単そうです。ここで vector でのソートの仕方と、要素が pair の時にソートした結果がどうなるのかをまとめてみます。
- vector は begin と end の二つのメソッドを使って先頭と末尾のイテレータを取得できる
- A という vector の要素を昇順ソートしたいときは、 sort(A.begin(), A.end()); で行える(algorithm というヘッダーファイルをインクルードしておく必要がある)
- pair の要素をソートする際には、各要素は辞書に的比較される
実際に pair を要素にした vector を使ってみました。(追記：pairを使うときは utility をインクルードする必要があります)
#include <iostream> #include <vector> #include <algorithm> #include <utility> using namespace std; int main(){ vector<pair<int,int> > A(5); // 要素数5の vector の宣言 A[0].first = 2; // A[0]の一つ目の要素に2を代入 A[0].second = 4; // A[0]の二つ目の要素に4を代入 A[1].first = 3; // A[1]の一つ目の要素に3を代入 A[1].second = 1; // A[1]の二つ目の要素に1を代入 A[2].first = 1; // A[2]の一つ目の要素に1を代入 A[2].second = 5; // A[2]の二つ目の要素に5を代入 A[3].first = 1; // A[3]の一つ目の要素に1を代入 A[3].second = 2; // A[3]の二つ目の要素に2を代入 A[4].first = 4; // A[4]の一つ目の要素に4を代入 A[4].second = 6; // A[4]の二つ目の要素に6を代入 cout << "現在の要素は" << endl; // 現在の要素を出力 for(int i=0;i < (int)A.size();i++){ cout << "(" << A[i].first << "," << A[i].second << ")" << " "; } cout << endl; sort(A.begin(), A.end());// Aを昇順ソートする cout << "現在の要素は" << endl; // 現在の要素を出力 for(int i=0;i < (int)A.size();i++){ cout << "(" << A[i].first << "," << A[i].second << ")" << " "; } cout << endl; }
実行結果は以下のようになります。
現在の要素は (2,4) (3,1) (1,5) (1,2) (4,6) 現在の要素は (1,2) (1,5) (2,4) (3,1) (4,6)
ちゃんと辞書順に比較されていることが分かります。ここで C 問題について考えてみます。C 問題は、エナジードリンクが安い店から順番に、できるだけ多くのエナジードリンクを買うのが最適解です。そのために、エナジードリンクが安い順に、お店をソートすることを考えます。しかし、価格についてだけをソートすると、その店で買える最大本数が分からなくなってしまいます。なので、各要素が価格と最大数を表している、pair の vectorを考えます。そして一つ目の要素にその店の価格を、二つ目の要素をその店で買える最大本数を格納します。これをソートすると、お店は価格が安い順にソートされます。価格が同じ店については、最大本数が少ない方が先になります。少ない方から買っても、多い方から買っても解に影響はありません。これらを踏まえた、C 問題の解答が次のコードです。
#include <iostream> #include <algorithm> #include <functional> #include <utility> #include <vector> using namespace std; int main(){ long int N, M; cin >> N >> M; vector<int> A(N), B(N); for(int i=0;i<N;i++){ cin >> A[i] >> B[i]; } vector<pair<long int,long int>> buy(N); for(int i=0;i<N;i++){ buy[i].first = A[i]; buy[i].second = B[i]; } sort(buy.begin(), buy.end()); long int sum = 0; for(int i = 0;i<N;i++){ if(M <= 0) break; long int m = min(buy[i].second,M); sum += buy[i].first * m; M -= m; } cout << sum << endl; }
出力する値である合計価格が、32ビット整数に収まらないことがあります。このときにlong int を使っていないと、オーバーフローしてしまうので注意が必要です。
