競技プログラミング風標準C++ライブラリ入門【第3回】

TsudaNobuhide

競技プログラミング風標準C++ライブラリ入門【第3回】

今回も、標準C++ライブラリ入門のための競技プログラミング風問題を解いて、標準C++ライブラリに親しんでいただきたい。

問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。コードを完成させて、「Good Job!」を表示させていただきたい。グッドラック！

指定要素数（難易度：★★☆☆☆）

問題

const vector<int>参照型のv, カウントする要素の値 d を受け取り、d に等しい要素の数を返す関数 int my_count(const vector<int>& v, int d) を実装しなさい。

例えば {0, 3, 2, 3} と 3 が渡されると 2 を、{9, 8} と 9 が渡されると 1 を返す。
[java] #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
int my_count(const vector<int>& v, int d) {
return 0; // ToDo: 標準ライブラリの関数を使い、d に等しい v の要素数を返す
}
int main()
{
DO_TEST( my_count(vector<int>({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}), 1) == 2 );
DO_TEST( my_count(vector<int>({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}), 10) == 0 );
DO_TEST( my_count(vector<int>({3, 3, 3, 3, 3}), 3) == 5 );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・コンテナクラスの特定要素数を取得するには、int std::count(first, last, value) 関数を使うんだぞ。

解答例

[java] int my_count(const vector<int>& v, int d) {
return count(v.begin(), v.end(), d);
}
[/java]

解説

コンテナの要素をコンテナクラスの特定要素数を取得するには、int std::count(first, last, value) 関数を使う。 first, last はコンテナの先頭, 末尾+1だ。そして value はカウントするデータ値を指定する。

文字列配列ソート（難易度：★★☆☆☆）

問題

vector<string>参照型のlstを受け取り、文字列を昇順（辞書順）にソートする関数 void my_sort(vector<string>& lst) を実装しなさい。

例えば、{“abc”, “xz”, “ab”, “ac”, “abb”, “xyz”} が渡された場合、結果は {“ab”, “abb”, “abc”, “ac”, “xyz”, “xz”} となる。
[java] #include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
void my_sort(vector<string>& lst) {
// ToDo: 標準ライブラリの関数を使い、lst の要素を昇順ソートする
}
int main()
{
vector<string> vs = {"abc", "xz", "ab", "ac", "abb", "xyz"};
my_sort(vs);
DO_TEST( vs == vector<string>({"ab", "abb", "abc", "ac", "xyz", "xz"}) );
vs.clear();
my_sort(vs);
DO_TEST( vs.empty() );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・コンテナクラスの要素を昇順ソートするには、void std::sort(first, last) 関数を使うんだぞ。
・first, last はソート範囲を示すイテレータだぞ。

解答例

[java] void my_sort(vector<string>& lst) {
sort(lst.begin(), lst.end()); // lst の要素を昇順ソート
}
[/java]

解説

コンテナクラスの要素を昇順ソートするには、void std::sort(first, last) 関数を使う。 first, last はソート範囲の先頭, 末尾+1で、配列アドレスまたはイテレータで指定可能だぞ。

指定要素削除（難易度：★★☆☆☆）

問題

vector<int>参照型のlst, 削除する値aを引数にとり、lstの要素でaに等しいものをすべて削除する関数 void my_remove(vector<int>& v, int a) を実装しなさい。

例えば v: {1, 2, 3} と 2 が渡された場合は v: {1, 3} となり、v: {3, 1, 4, 1} と 1 が渡された場合は v: {3, 4} となる。
[java] #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define DO_TEST(exp) do_test(exp, __LINE__)
void do_test(bool b, int line) {
if( b ) return; // OK
cout << "\nNG at line " << line << "\n";
exit(1);
}
void my_remove(vector<int>& v, int a) {
// ToDo: 標準ライブラリの関数を使い、a に等しい v の要素を削除する
}
int main()
{
vector<int> v0 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
my_remove(v0, 8);
DO_TEST( v0 == vector<int>({3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}) );
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
my_remove(v, 1);
DO_TEST( v == vector<int>({3, 4, 5, 9, 2, 6, 5, 3, 5}) );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・コンテナクラスの指定要素を削除するには、Iterator std::remove(first, last, d) 関数を使うんだぞ。
・first, last は削除対象範囲の先頭, 末尾+1で、d は削除する要素の値だぞ。
・std::remove() は、コンテナそのものの要素数を減らさず、削除されたデータ分縮小された範囲の末尾+1を指すイテレータを返すぞ。

解答例

[java] void my_remove(vector<int>& v, int a) {
auto itr = remove(v.begin(), v.end(), a); // 要素aを削除
v.resize(itr – v.begin()); // 不要な要素を削除
}
[/java]

解説

コンテナクラスの特定要素を削除するには、Iterator std::remove(first, last, d) 関数を使う。 first, last は削除対象範囲の先頭, 末尾+1で、d は削除する要素の値を指定する。
std::remove() は削除されたデータ分縮小された範囲の末尾+1を指すイテレータを返すので、 v.resize(itr – v.begin()); を実行し、引数で渡された v の不要になった要素を削除する必要があるぞ。