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

TsudaNobuhide

競技プログラミング風標準C++ライブラリ入門【第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} となる。
[java] #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;
}
[/java]

ヒント

・降順ソートを行うには std::sort(first, last, pred) を使うんだぞ。
・first, last はソート範囲だぞ。
・pred はソート時に使用される要素比較関数・ラムダ式・ファンクタのどれかだぞ。

解答例

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

解説

降順ソートを行うには std::sort(first, last, pred) を使う。
first, last はソート範囲だ。コンテナ全体をソースする場合であれば、begin(), end() を使用し、本問題のように配列ソートであれば、範囲先頭アドレス、範囲末尾アドレス+1 を指定する。
pred は、ソート時に使用される要素比較関数・ラムダ式・ファンクタのどれかだ。解答例では最もわかりやすいラムダ式を使用している。定義済みファンクタである std::greater() を使うことも可能だ。

16進数文字列変換（難易度：★★★☆☆）

問題

int型の値を受け取り、それを16進数文字列（10～15 を ‘a’～’f’ で表現）に変換する関数 string hexstr(int h) を実装しなさい。

例えば、100 が渡された場合は “64” を、10 が渡された場合は “a” を返す。
[java] #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;
}
[/java]

ヒント

・数値を16進数に変換するには、std::stringstream を使うと簡単だぞ。
・<< 演算子で数値を stringstream オブジェクトに追加すると、文字列に変換されるぞ。
・その前に std::hex を stringstream オブジェクトに追加すると16進数モードとなるぞ。

解答例

[java] string hexstr(int h) {
stringstream ss; // 文字列ストリーム
ss << std::hex << h; // 16進数文字列変換
return ss.str(); // 文字列取り出し
}
[/java]

解説

数値を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 が返る。
[java] #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;
}
[/java]

ヒント

・指定値以上になる最初の位置をバイナリサーチするには std::lower_bound(first, last, value) を使うぞ。
・first, last は探索範囲で、あらかじめ昇順ソートされている必要があるぞ。
・std::lower_bound() はイテレータを返すので、それを配列インデックスに変換する必要があるぞ。

解答例

[java] int my_lower_bound(const string* ar, int SZ, const string& str) {
auto itr = lower_bound(ar, ar + SZ, str); // 検索結果はイテレータで返る
return itr – ar; // 配列添字に変換
}
[/java]

解説

指定値以上になる最初の位置をバイナリサーチするには std::lower_bound(first, last, value) を使う。 first, last は探索範囲で、本問題の場合は通常配列なので、ar, ar+SZ を渡すとよい。
std::lower_bound() はイテレータを返すが、本問題の場合は配列アドレスを渡しているので、最初に str 以上になる要素アドレスを返す。なので itr – ar で配列インデックスに変換している。