シーズン2 全体目次:
↓第5回
これまでに競技プログラミング風 標準C++ライブラリ入門 を4回にわたりお届けしたが、各方面に好評だったので、 おかわり(シーズン2)として【第5回】~【第8回】をお届けする。
標準C++ライブラリを知っていれば比較的簡単な問題をたくさん解いて、 標準C++ライブラリに親しんでいただこうというのが本連載の趣旨だ。
各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ
(ideonなど)で保存・ビルド・実行し、
NGが出ないようにテストコードの「ToDo:」部分のコードを完成させてほしい。
「ヒント」「解答例」「解説」はデフォルトでは非表示になっており、中身を読みたい場合は【show】ボタンを押せば表示される。 これらをすぐに読むのではなく、ちゃんと解答を考え、使用する標準ライブラりのクラス・関数をweb検索して勉強し、 コード記述・ビルド・実行してからそれらを読むのを強く推奨する。なにごとも自分で考え、いろいろ試した上で、解答などを見るようにするのが肝要だ。 その方が解答が印象に残り問題解決方法が記憶に定着しやすいのだ。
目次:
int 型引数を受け取って、それを文字列に変換したものを返す string itostr(int) を定義しなさい。
例えば、123 が引数で渡された場合は "123" を、-99 が渡された場合は "-99" を返す。
#include <iostream> // 標準入出力ライブラリ #include <string> 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); } string itostr(int a) { return ""; // ToDo: 標準関数を使い、ここを書き換えて、a の値を文字列に変換したものを返す } int main() { DO_TEST( itostr(123) == "123" ); DO_TEST( itostr(-99) == "-99" ); cout << "\nGood Job!\n"; return 0; }
string itostr(int a) { return to_string(a); // 引数の値を文字列に変換 }
a の値を文字列に変換するには string std::to_string(a) をコールするだけだぞ。
ちなみに、引数の型は int 型だけではなく double 型などでもOKだぞ。
string型の参照変数 str1, str2 を受け取り、その内容を交換する関数 void my_swap(string& str1, string& str2) を実装しなさい。
例えば、str1: "abc", str2: "xyzzz" のときに、my_swap(str1, str2) をコールすると、str1: "xyzzz", str2: "abc" となる。
#include <iostream> // 標準入出力ライブラリ #include <string> 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); } void my_swap(string& str1, string& str2) { // ToDo: 標準関数を使い、ここを書き換えて、str1 と str2 の内容を交換する } int main() { string str1 = "abc", str2 = "xyzzz"; my_swap(str1, str2); DO_TEST( str1 == "xyzzz" ); DO_TEST( str2 == "abc" ); cout << "\nGood Job!\n"; return 0; }
void my_swap(string& str1, string& str2) swap(str1, str2); // str1, str2 の内容を交換 }
変数 a, b の内容を交換するには void std::swap(a, b) を使うだけだ。
ちなみに、std::swap(a, b) を使わない場合は、以下のように記述する。
void my_swap(string& str1, string& str2) auto t = str1; // 一旦別の変数に退避 str1 = str2; // str1 にコピー str2 = t; // 退避していた値を str2 にコピー }
double型引数で実数部 r、虚数部 i をを受け取り、complex
例えば、gen_complex(1, 2) は、実数1, 虚数2の複素数オブジェクトを返す。
#include <iostream> // 標準入出力ライブラリ #include <complex> 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); } complex<double> gen_complex(double r, double i) { return 0; // ToDo: 標準関数を使ってここを書き換え、実数r, 虚数i の複素数を返す } int main() { auto c1 = gen_complex(1, 2); DO_TEST( real(c1) == 1.0 ); DO_TEST( imag(c1) == 2.0 ); cout << "\nGood Job!\n"; return 0; }
complex<double> gen_complex(double r, double i) { return complex<double>(r, i); // 実数r, 虚数i の複素数を返す }
標準C++ライブラリには complex という複素数クラスが用意されている。
このクラスはテンプレートクラスなので、complex<double> のように、実数・虚数部の型を指定する必要がある。
解答例のようにコンストラクタの引数に実数・虚数部の値を渡せば、その値の複素数オブジェクトを生成してくれる。
↓第6回
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック!
目次:
引数で const vector<int>& 型の数値リストを受け取り、3の倍数の要素数を返す関数 int count3x(const vector<int>& lst) を実装しなさい。
例えば、{3, 1, 4, 6, 0, 2} が渡された場合は 3 を、{-3, 1, 4, 6, 2} が渡された場合は 2 を返す。
#include <iostream> // 標準入出力ライブラリ #include <algorithm> #include <vector> 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); } int count3x(const vector<int>& lst) { return 0; // ToDo: 標準関数を使ってここを書き換え、lst 中の3の倍数の数を返す } int main() { vector<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; DO_TEST( count3x(lst) == 4 ); vector<int> lst2 = {3, 1, 4, 3}; DO_TEST( count3x(lst2) == 2 ); cout << "\nGood Job!\n"; return 0; }
int count3x(const vector<int>& lst) { return count_if(lst.begin(), lst.end(), [](int a) { return a % 3 == 0; }); }
条件を満たす要素数をカウントするには int count_if(first, last, pred) を使うとよい。 この問題ではコンテナの要素をカウントするので、lst.begin(), lst.end() を指定する。 3の倍数かどうかは a%3 が0かどうかを判定すればよいので、ラムダ式を使って、解答例のように記述する。
count_if() の条件部分には、ラムダ式だけでなく、関数・ファンクタを指定することができる。
関数を使用する場合は、以下のように記述する。コード行数は増えるが、初心者にはこちらの方がわかりやすいかもしれない。
int is3x(int a) { return a % 3 == 0; } // 3の倍数かどうかを判定する関数 int count3x(const vector& lst) { return count_if(lst.begin(), lst.end(), is3x); // 第3引数に、関数指定 }
() 演算子を定義したクラス(これはファンクタと呼ぶ)を指定することもできる。
ファンクタはC++にラムダ式がなかった頃の遺物で、現在ではラムダ式を使うのが普通だ。
こういう書き方もあるという紹介だ。
struct Chk3x { // 3の倍数かどうかを判定するファンクタクラス bool operator()(int a) { return a % 3 == 0; } // () 演算子定義 }; int count3x(const vector& lst) { return count_if(lst.begin(), lst.end(), Chk3x()); // 第3引数はファンクタ指定 }
int 型の値、文字幅を引数で受け取って、それを文字列に変換したものを返す string itostr(int a, int wd) を定義しなさい。
単純に文字列化したものの文字数が wd 未満の場合は、先頭に半角空白(' ')を付加し、文字数がwdになるようにしなさい。
例えば、123, 4 が引数で渡された場合は " 123" を、-99, 2 が渡された場合は "-99" を返す。
#include <iostream> // 標準入出力ライブラリ #include <string> 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); } string itostr(int a, int wd) { return ""; // ToDo: 標準関数を使い、ここを書き換えて、a の値を文字幅wdの文字列に変換したものを返す } int main() { DO_TEST( itostr(123, 2) == "123" ); DO_TEST( itostr(123, 4) == " 123" ); DO_TEST( itostr(-99, 2) == "-99" ); DO_TEST( itostr(-99, 5) == " -99" ); cout << "\nGood Job!\n"; return 0; }
string itostr(int a, int wd) { auto txt = to_string(a); // 引数の値を文字列に変換 while( txt.size() < wd ) // 文字幅が足りない場合は txt = ' ' + txt; // 先頭に半角空白を付加 return txt; }
a の値を文字列に変換するには to_string(a) をコールするだけだ。
文字幅を指定幅にするには、指定幅に足りない間ループし、先頭に半角空白(' ')を負荷するとよい。
第1引数で const vector<string>& 型の文字列リストを引数で受け取り、 各文字列を昇順にソートし各文字列の出現数を vector<int>& 型第2引数に格納する関数 void my_count(const vector<string>& lst, vector<int>& result) を実装しなさい。
例えば、{"abc", "a", "abb", "abc", "abc", "a"} が第1引数で渡された場合、第2引数に {2, 1, 3} が設定される ("a": 2個、"abb": 1個、"abc": 3個)。
#include <iostream> // 標準入出力ライブラリ #include <string> #include <vector> #include <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); } void my_count(const vector<string>& lst, vector<int>& result) { // ToDo: 標準関数を使い、ここを書き換えて、lst の各文字列の出現数を辞書順にしたものを result に格納 } int main() { vector<string> lst = {"abc", "a", "abb", "abc", "abc", "a"}; vector<int> result; my_count(lst, result); DO_TEST( result == vector<int>({2, 1, 3}) ); cout << "\nGood Job!\n"; return 0; }
void my_count(const vector<string>& lst, vector<int>& result) { map<string, int> mp; // カウント用 map for (const auto& x : lst) mp[x] += 1; // 各文字列をカウント result.clear(); // 結果格納コンテナをクリア for (auto x : mp) result.push_back(x.second); // map は昇順にソートされているので、文字列数を順に取り出し格納 }
文字列を昇順カウントするには std::map<string, int> 型の mp を使うとよい。 各文字列の出現数をカウントするには、単に mp[文字列] += 1; とするとよい(mp[文字列] は自動的に0に初期化される)。 map の要素は自動的に昇順ソートされているので、拡張for文で順に要素をアクセスすると、文字列数を順に取り出すことができる。
↓第7回
今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。
問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック!
目次:
int[] 型のar, 要素数szを受け取り、要素を降順にソートする関数 void sortArrayDesc(int ar[], int sz) を実装しなさい。
例えば、{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5} が渡された場合は、結果は {9, 6, 5, 5, 4, 3, 3, 2, 1, 1} となる。
#include <iostream> #include <vector> #include <algorithm> 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 sortArrayDesc(int ar[], int sz) { // ToDo: 標準ライブラリの関数を使って、サイズ sz の配列 ar をソートする } int main() { int ar0[] = {123}; const int sz0 = sizeof(ar0)/sizeof(int); sortArrayDesc(ar0, sz0); DO_TEST( vector<int>(ar0, ar0+sz0) == vector<int>({123}) ); int ar[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; const int sz = sizeof(ar)/sizeof(int); sortArrayDesc(ar, sz); DO_TEST( vector<int>(ar, ar+sz) == vector<int>({9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1}) ); cout << "\nGood Job!\n"; return 0; }
void sortArrayDesc(int ar[], int sz) { //sort(ar, ar + sz, std::greater<int>()); sort(ar, ar + sz, [](const auto& lhs, const auto& rhs) { return lhs > rhs; }); }
降順ソートを行うには std::sort(first, last, pred) を使う。
first, last はソート範囲だ。
コンテナ全体をソースする場合であれば、begin(), end() を使用し、本問題のように配列ソートであれば、
範囲先頭アドレス、範囲末尾アドレス+1 を指定する。
pred は、ソート時に使用される要素比較関数・ラムダ式・ファンクタのどれかだ。
解答例では最もわかりやすいラムダ式を使用している。定義済みファンクタである std::greater() を使うことも可能だ。
int型の値を受け取り、それを16進数文字列(10~15 を 'a'~'f' で表現)に変換する関数 string hexstr(int h) を実装しなさい。
例えば、100 が渡された場合は "64" を、10 が渡された場合は "a" を返す。
#include <iostream> // 標準入出力ライブラリ #include <sstream> #include <string> 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); } string hexstr(int h) { return ""; // ToDo: 標準関数を使い、ここを書き換えて、h を16進数文字列に変換したものを返す } int main() { DO_TEST( hexstr(0x123) == "123" ); DO_TEST( hexstr(123) == "7b" ); DO_TEST( hexstr(-1) == "ffffffff" ); cout << "\nGood Job!\n"; return 0; }
string hexstr(int h) { stringstream ss; // 文字列ストリーム ss << std::hex << h; // 16進数文字列変換 return ss.str(); // 文字列取り出し }
数値を16進数に変換するには std::stringstream を使うと簡単だ。
「stringstream ss;」で stringstream オブジェクトを生成し、それに対して << 演算子で値を渡してあげると、文字列に自動的に変換してくれる。
ただし、本問題では 16進数に変換しなくてはいけないので、先に「<< std::hex」を記述し、16進数モードにしてあげる。
「ss.str()」で、stringstream が保持している文字列を取得できるので、最後にそれを返すだけだ。
昇順にソートされた文字列配列 const string* ar、文字列数 SZ、検索する文字列 str を引数で受け取り、 ar[ix] >= str となる最初の ix を返す二分探索関数 int my_lower_bound(const string* ar, int SZ, const string& str) を実装しなさい。
例えば、{"a", "bb", "bbb", "bbb", "cde"} に対して "a" を検索した場合は 0 が、"bb" を検索した場合は 1 が返る。 "ax" のようにリストに無い文字列を検索した場合は "ax" より大きい最初の文字列は "bb" なので 1 が返る。
#include <iostream> #include <vector> #include <algorithm> 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_lower_bound(const string* ar, int SZ, const string& str) { // ToDo: 標準ライブラリの関数を使って、昇順ソートされた文字列配列から str を二分検索し、そのインデックスを返す return 0; } int main() { string ar[] = {"a", "bb", "bbb", "bbb", "cde"}; const int SZ = sizeof(ar) / sizeof(string); DO_TEST(my_lower_bound(ar, SZ, "bbb") == 2); DO_TEST(my_lower_bound(ar, SZ, "ab") == 1); DO_TEST(my_lower_bound(ar, SZ, "z") == SZ); cout << "\nGood Job!\n"; return 0; }
int my_lower_bound(const string* ar, int SZ, const string& str) { auto itr = lower_bound(ar, ar + SZ, str); // 検索結果はイテレータで返る return itr - ar; // 配列添字に変換 }
指定値以上になる最初の位置をバイナリサーチするには std::lower_bound(first, last, value) を使う。
first, last は探索範囲で、本問題の場合は通常配列なので、ar, ar+SZ を渡すとよい。
std::lower_bound() はイテレータを返すが、本問題の場合は配列アドレスを渡しているので、最初に str 以上になる要素アドレスを返す。
なので itr - ar で配列インデックスに変換している。
↓第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; }
void permutationDesc(string str, vector& lst) { lst.clear(); // lst クリア // 全順列が生成されるように、str の各文字を降順ソート sort(str.begin(), str.end(), [](const auto& lhs, const auto& rhs) { return lhs > rhs; }); //sort(str.begin(), str.end(), greater()); do { lst.push_back(str); // 生成された順列テキストを lst に保存 } while (prev_permutation(str.begin(), str.end())); // 前の順列を生成 }
文字列のすべての順列を降順に生成するには prev_permutation(str.begin(), str.end()) を用いる。
結果文字列は降順に生成されるので、最初に文字列の各文字を降順ソートしておく。
降順ソートするには std::sort() を使い、第3引数に比較関数を指定する。
解答例のようにラムダ関数を使用してもよいし、お好みで std::greater() ファンクタを使ってもよい。
lst は最初に内容をクリアし、生成された順列文字列を push_back() で追加していく。
第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; }
void my_set_intersection(const vector& lst1, const vector & lst2, vector & u) { u.resize(min(lst1.size(), lst2.size())); // lst1, lst2 の小さい方の分の領域を確保しておく auto itr = set_intersection(lst1.begin(), lst1.end(), // 共通要素を取り出す範囲その1 lst2.begin(), lst2.end(), // 共通要素を取り出す範囲その2 u.begin()); // u の先頭イテレータ u.resize(itr - u.begin()); }
共通要素を取り出すには Iterator std::set_intersection(first1, last1, first2, last2, iout) を使う。 first1, last1, first2, last2 は共通要素を取り出すデータの範囲だ。具体的にはコンテナクラスのイテレータか配列アドレスを指定する。 最後の iout 引数は共通要素を格納する場所位置へのイテレータだ。コンテナクラスのイテレータか配列アドレスを指定可能だが、 領域を自動的には確保してくれないので、十分な領域をあらかじめ確保しておく必要がある。 そのためには、解答例のように、2つのコンテナオブジェクトサイズの最小値を確保しておけばよい。 最後に、set_intersection() が返すイテレータを使い、共通要素を格納する u を resize() し、余分な領域を削除しておく。
第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; }
bool isMatch(const char* str, const char* re) { return regex_match(string(str), regex(re)); }
文字列が正規表現にマッチしているかどうかの判定は std::regex_match(string, regex) を使う。
string は判定する文字列で、regex は正規表現オブジェクト。
解答例のように、文字列をそれぞれのオブジェクトに変えてコールするだけだ。
下記のように分けて記述してもよいが、解答例のように1行で書くほうが簡潔で筆者の好みだ。
string s(str); regex r(re); return regex_match(s, re);
標準C++ライブラリ入門向けの競技プログラミング風問題のおかわりを12問解いていただいた。
標準C++ライブラリを知って、使いこなせれば、いろいろなコードを楽に、かつ高品質に書けることを実感していただけたものと思っている。
本連載を機に標準C++ライブラリに興味を持っていただき、使いこなせるようになっていただけたら幸いである。