競技プログラミング風 標準C++ライブラリ入門【第8回】
今回で本シリーズも最後だ。競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。
問題を理解したら、テストコードをコンパイル・実行してほしい。そのままだと実行時に「NG」が表示されるので、 コードを完成させて、「Good Job!」を表示させるのが目標だ。グッドラック!
目次
降順順列生成(難易度:★★★☆☆)
文字列を第1引数で受け取り、その文字列のすべての順列を辞書順の逆の順序(降順)で第2引数に格納する関数 void permutationDesc(string str, vector<string>& lst) を実装しなさい。
例えば、”abc” が引数で渡された場合は、{“cba”, “cab”, “bca”, “bac”, “acb”, “abc”} が第2引数に格納される。
“cba” のように各文字が昇順でない場合、”aab” のように重複がある場合などにもちゃんと対応しなさい。
#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 permutationDesc(string str, vector<string>& lst) { // ToDo: 標準ライブラリの関数を使い、降順に順列をすべて生成し、lst に格納する } int main() { vector<string> lst; permutationDesc("abc", lst); DO_TEST( lst == vector<string>({"cba", "cab", "bca", "bac", "acb", "abc"}) ); permutationDesc("cba", lst); DO_TEST( lst == vector<string>({"cba", "cab", "bca", "bac", "acb", "abc"}) ); permutationDesc("aba", lst); DO_TEST( lst == vector<string>({"baa", "aba", "aab"}) ); cout << "\nGood Job!\n"; return 0; }
共通要素取得(難易度:★★★☆☆)
第1・2引数に、要素が昇順ソートされた const vector<int>& 型の lst1, lst2 が渡され、 その共通要素を vector<int>& 型の第3引数に格納する関数 void my_set_intersection(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) を実装しなさい。
例えば、{1, 2, 3, 5, 9} と {2, 3, 4, 9} が渡された場合は、共通要素をまとめた {2, 3, 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_intersection(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_intersection(lst1, lst2, u); DO_TEST( u == vector<int>({2, 3, 9}) ); cout << "\nGood Job!\n"; return 0; }
正規表現マッチ(難易度:★★★☆☆)
第1引数でconst char*型文字列を、第2引数でconst char*型正規表現文字列を受け取り、それらがマッチするかどうかを判定する関数 bool isMatch(const char* str, const char* re) を実装しなさい。
例えば、isMatch(“acb”, “[a-c]+”) は true を、isMatch(“xyz”, “[a-c]+”) は false を返す。
なお、isMatch(“aXb”, “[a-c]+”) のように、一部分だけマッチする場合は false を返すものとする。
#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 isMatch(const char* str, const char* re) { // ToDo: 標準ライブラリの関数を使い、lst1, lst2 の共通要素を u に格納する return true; } int main() { DO_TEST( isMatch("123", "[0-9]+") ); DO_TEST( !isMatch("123z", "[0-9]+") ); DO_TEST( !isMatch("a123", "[0-9]+") ); DO_TEST( isMatch("abc", "(abc|xyzzz)") ); DO_TEST( isMatch("xyzzz", "(abc|xyzzz)") ); 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++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |