競技プログラミング風 標準C++ライブラリ入門【第12回】
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック!
目次
和集合要素取得(難易度:★★★☆☆)
第1・2引数に、要素が昇順ソートされた const vector<int>& 型の lst1, lst2 が渡され、 その昇順和集合(重複要素を削除し、マージしたもの)を vector<int>& 型の第3引数に格納する関数 void my_set_union(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) を実装しなさい。
例えば、{1, 2, 3, 5, 9} と {2, 3, 4, 9} が渡された場合は、昇順和集合の {1, 2, 3, 4, 5, 9} を第3引数に設定する。
#include <iostream> #include <algorithm> #include <string> #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_set_union(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) { // ToDo: 標準ライブラリの関数を使い、lst1, lst2 の昇順和集合を u に格納する } int main() { vector<int> lst1 = {1, 2, 3, 5, 9}; vector<int> lst2 = {2, 3, 4, 9}; vector<int> u; my_set_union(lst1, lst2, u); DO_TEST( u == vector<int>({1, 2, 3, 4, 5, 9}) ); cout << "\nGood Job!\n"; return 0; }
辞書登録・参照(難易度:★★★☆☆)
テストコードの ToDo 部分を修正し、文字列をキーとし、int型数値を値として保持する unordered_map型辞書オブジェクトを定義し、 その辞書にキー・値を登録する関数 void doInsert(const string& key, int value)、 辞書を検索し、キーに対応する値を返す関数 int getValue(const string& key) を実装しなさい。
ただし、辞書にキーが登録されていない場合は -1 を返すものとする。
例えば、doInsert(“abc”, 123) をコール後に getValue(“abc”) をコールすると、123 が返ってくる。
#include <iostream> // 標準入出力ライブラリ #include <string> #include <unordered_map> using namespace std; // 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); } // ToDo: 標準C++ライブラリのクラスを使って、辞書オブジェクトをここで定義 void doInsert(const string& key, int value) { // ToDo: 標準関数を使い、ここを書き換えて、辞書に (key, value) を登録 } int getValue(const string& key) { // ToDo: 標準関数を使い、ここを書き換えて、辞書中の key の値を返す // 辞書に key が登録されていない場合は -1 を返すものとする return 0; } int main() { doInsert("abc", 1); doInsert("xyzzz", 2); doInsert("bc", 3); doInsert("bc", 4); // 上書きするものとする DO_TEST( getValue("abc") == 1); DO_TEST( getValue("ab") == -1); DO_TEST( getValue("bc") == 4); cout << "\nGood Job!\n"; return 0; }
正規表現検索(難易度:★★★☆☆)
第1引数でconst char*型被検索文字列を、第2引数でconst char*型正規表現文字列を受け取り、 それらが正規表現が被検索文字列に含まれるかどうかを返す関数 bool my_regex_find(const char* str, const char* re, int& ix, int& sz) を実装しなさい。
なお、正規表現が被検索文字列に含まれる場合は、第3引数にその位置を、第4引数にマッチした文字数を設定するものとする。
例えば、my_regex_find(“acb”, “[a-c]+”, ix, sz) は true を返し、ix:0, sz:3 となる。
#include <iostream> #include <string> #include <regex> 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); } bool my_regex_find(const char* str, const char* re, int& ix, int& sz) { // ToDo: 標準ライブラリの関数を使い、正規表現に最初にマッチする位置を ix に、長さを sz に設定 // ToDo: マッチする場合は true を、しない場合は false を返すコードを記述 return true; } int main() { int ix, sz; DO_TEST( my_regex_find("123", "[0-9]+", ix, sz) && ix == 0 && sz == 3 ); DO_TEST( my_regex_find("-123-", "[0-9]+", ix, sz) && ix == 1 && sz == 3 ); DO_TEST( my_regex_find("--123123--123--", "[0-9]+", ix, sz) && ix == 2 && sz == 6 ); DO_TEST( my_regex_find("--123--ax123--", "[a-z]+[0-9]+", ix, sz) && ix == 7 && sz == 5 ); cout << "\nGood Job!\n"; return 0; }
さいごに
標準C++ライブラリ入門向けの競技プログラミング風問題のさらにおかわりを12問解いていただいた。
標準C++ライブラリを知って、使いこなせれば、いろいろなコードを楽に、かつ高品質に書けることを実感していただけたものと思っている。
本連載を機に標準C++ライブラリに興味を持っていただき、使いこなせるようになっていただけたら幸いだ。
関連記事

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

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

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

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

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

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

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

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

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

競技プログラミング風 標準C++ライブラリ入門【第3回】
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |