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

TsudaNobuhide

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

今回で本シリーズも最後だ。競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。

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

降順順列生成（難易度：★★★☆☆）

問題

文字列を第1引数で受け取り、その文字列のすべての順列を辞書順の逆の順序（降順）で第2引数に格納する関数 void permutationDesc(string str, vector<string>& lst) を実装しなさい。

例えば、”abc” が引数で渡された場合は、{“cba”, “cab”, “bca”, “bac”, “acb”, “abc”} が第２引数に格納される。

“cba” のように各文字が昇順でない場合、”aab” のように重複がある場合などにもちゃんと対応しなさい。
[java] #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;
}
[/java]

ヒント

・降順に順列を生成するには、 prev_permutation(first, last) 関数を使うんだぞ。
・すべての順列を降順に生成するには、文字列の各文字を降順にソートしておく必要があるぞ。

解答例

[java] 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())); // 前の順列を生成
}
[/java]

解説

文字列のすべての順列を降順に生成するには 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引数に設定する。
[java] #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;
}
[/java]

ヒント

・共通要素を取り出すには Iterator std::set_intersection(first1, last1, first2, last2, itr) を使うんだぞ。
・first1, last1, first2, last2 は共通要素を取り出す昇順ソート済みのデータ範囲だぞ。
・itr は共通要素を格納する場所を示すイテレータだぞ。
・set_intersection() は共通要素を格納した最後+1を返すぞ。

解答例

[java] 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());
}
[/java]

解説

共通要素を取り出すには 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 を返すものとする。
[java] #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;
}
[/java]