Developer

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

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

競技プログラミング風 標準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;
}
ヒント

・昇順な和集合を取り出すには Iterator std::set_union(first1, last1, first2, last2, itr) を使うんだぞ。
・first1, last1, first2, last2 は和集合要素を取り出す昇順ソート済みのデータ範囲だぞ。
・itr は和集合を格納する場所を示すイテレータだぞ。
・結果を格納するのに充分な領域を予め確保しておく必要があるぞ。
・set_union() は和集合を格納した最後の要素へのイテレータ+1を返すぞ。

解答例
void my_set_union(const vector<int>& lst1, const vector<int>& lst2, vector<int>& u) {
    u.resize(lst1.size() + lst2.size());    //  lst1, lst2 の合計サイズ分の領域を確保しておく
    auto itr = set_union(lst1.begin(), lst1.end(),   //  和集合要素を取り出す範囲その1
                         lst2.begin(), lst2.end(),   //  和集合要素を取り出す範囲その2
                         u.begin());     //  u の先頭イテレータ
    u.resize(itr - u.begin());      //  不要な要素を削除
    //u.erase(itr, u.end());      //  不要な要素を削除
}
解説

昇順の和集合要素を取り出すには Iterator std::set_union(first1, last1, first2, last2, iout) を使う。 first1, last1, first2, last2 は和集合要素を取り出すデータの範囲だ。具体的にはコンテナクラスのイテレータか配列アドレスを指定する。 最後の iout 引数は和集合要素を格納する場所位置へのイテレータだ。コンテナクラスのイテレータか配列アドレスを指定可能だが、 領域を自動的には確保してくれないので、十分な領域をあらかじめ確保しておく必要がある。 そのためには、解答例のように、2つのコンテナオブジェクトサイズのサイズ合計値を確保しておけばよい。 最後に、set_union() が返すイテレータを使い、和集合要素を格納する u を resize() し、余分な領域を削除しておく。 削除方法としては、回答例最後にコメントアウトしているように、「u.erase(itr, u.end())」と記述してもよい。 人によってはこの方がわかりやすいかもしれない。

辞書登録・参照(難易度:★★★☆☆)

問題

テストコードの 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;
}
ヒント

・キー・値のペアを登録・検索できる辞書を作るには map 類を使うといいぞ。
・本テストコードでは unordered_map をインクルードしてるので、それを使ってね、という趣旨だ。
・map 類はテンプレートクラスで、型指定時に map<キー型, 値型> と記述するんだぞ。
・dict を map類オブジェクトとするとき、「dict[キー] = 値;」でキー・値のペアを登録できるぞ。
・dict に key が登録済みかどうかを判定するには、dict.find(キー) と dict.end() を比較し、一致していれば未登録ってことだぞ。
・dict に key が登録済みであれば、dict[キー] で登録されている値を参照できるぞ。

解答例
unordered_map<string, int> g_dict;        //  辞書オブジェクト定義
void doInsert(const string& key, int value) {
    g_dict[key] = value;    //  辞書に (key, value) を登録
}
int getValue(const string& key) {
    if (g_dict.find(key) == g_dict.end())
        return - 1;     //  辞書に key が登録されていない場合
    return g_dict[key];   //  key に対応する値を返す
}
解説

回答例では std::map ではなく、std::unordered_map を使用している。前者はデータ構造として赤黒木を使用するが、 後者はハッシュを使用するので、より高速だ(挿入・参照の処理時間:前者は O(log N) だが、後者は O(1))。

まず、「unordered_map<string, int> g_dict;」で辞書オブジェクトを定義する。 テンプレート引数で string, int を指定しているので、文字列をキーとし、整数値を保持する辞書となる。

辞書にキー・値を追加するには、回答例のように「g_dict[キー] = 値;」と記述するだけだ。 すでにキー・値が登録されている場合は上書きされる。

辞書からキーを検索するには find() メンバ関数を使う。辞書に登録されていない場合は、end() が返されるので、仕様どおり -1 を返す。 辞書に登録済みの場合は g_dict[キー] で値を参照できるので、「return g_dict[キー];」と記述するだけだ。

正規表現検索(難易度:★★★☆☆)

問題

第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;
}
ヒント

・正規表現を利用するには regex クラスを使うぞ。
・被検索文字列から正規表現にマッチする部分があるかどうかを判定するには bool regex_search(str, result, re) 関数を使うんだぞ。
・str は被検索文字列のアドレス、result は検索結果を格納するオブジェクト、re は regex 型の正規表現オブジェクトだ。
・result は match_results<T> 型で、本問題の場合は char へのポインタなので、 「using cmatch = match_results<const char*>;」と宣言されている cmatch を使うんだぞ。

解答例
bool my_regex_find(const char* str, const char* re, int& ix, int& sz) {
    //  match_results result;
    cmatch result;      //  検索結果格納用オブジェクト
    if (!regex_search(str, result, regex(re)))      //  正規表現が str の一部とマッチしたか?
        false;          //  非マッチの場合
    ix = result[0].first - str;                 //  マッチ開始位置
    sz = result[0].second - result[0].first;    //  マッチした文字数
    return true;
}
解説

被検索文字列から正規表現にマッチする部分があるかどうかを判定するには regex_search(str, result, re) 関数を使う。
str は被検索文字列のアドレス、result は検索結果を格納するオブジェクト(詳しくは後術)、re は regex 型の正規表現オブジェクトだ。
result は match_results<T> 型で、本問題の場合は char へのポインタなので cmatch を使うぞ。
cmatch は「typedef match_results cmatch;」と定義されている。もし、string を検索する場合は smatch を使う。
cmatch オブジェクトには検索結果が格納される。result.size() で何箇所マッチしたかがわかり、 result[0] で最初にマッチした文字列の位置情報などを参照できる。result[0].first がマッチ開始位置、result[0].second がマッチ末尾位置+1だ。 これらの他にもいろいろな情報を保持している。詳しくはぐぐって調べてほしい。

さいごに

標準C++ライブラリ入門向けの競技プログラミング風問題のさらにおかわりを12問解いていただいた。
標準C++ライブラリを知って、使いこなせれば、いろいろなコードを楽に、かつ高品質に書けることを実感していただけたものと思っている。

本連載を機に標準C++ライブラリに興味を持っていただき、使いこなせるようになっていただけたら幸いだ。

関連記事

投稿が見つかりません。

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。