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

TsudaNobuhide

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

今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。

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

3の倍数カウント（難易度：★★☆☆☆）

問題

引数で const vector<int>& 型の数値リストを受け取り、3の倍数の要素数を返す関数 int count3x(const vector<int>& lst) を実装しなさい。

例えば、{3, 1, 4, 6, 0, 2} が渡された場合は 3 を、{-3, 1, 4, 6, 2} が渡された場合は 2 を返す。
[java] #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;
}
[/java]

ヒント

・条件を満たす要素数をカウントするには int count_if(first, last, pred) を使うんだぞ。
・first, last はカウントする範囲だぞ。
・pred は条件を判定する関数・ラムダ式・ファンクタのどれかだぞ。

解答例

[java] int count3x(const vector<int>& lst) {
return count_if(lst.begin(), lst.end(), [](int a) { return a % 3 == 0; });
}
[/java]

解説

条件を満たす要素数をカウントするには int count_if(first, last, pred) を使うとよい。この問題ではコンテナの要素をカウントするので、lst.begin(), lst.end() を指定する。 3の倍数かどうかは a%3 が0かどうかを判定すればよいので、ラムダ式を使って、解答例のように記述する。

count_if() の条件部分には、ラムダ式だけでなく、関数・ファンクタを指定することができる。
関数を使用する場合は、以下のように記述する。コード行数は増えるが、初心者にはこちらの方がわかりやすいかもしれない。
[java] int is3x(int a) { return a % 3 == 0; } // 3の倍数かどうかを判定する関数
int count3x(const vector& lst) {
return count_if(lst.begin(), lst.end(), is3x); // 第3引数に、関数指定
}
[/java] () 演算子を定義したクラス（これはファンクタと呼ぶ）を指定することもできる。
ファンクタはC++にラムダ式がなかった頃の遺物で、現在ではラムダ式を使うのが普通だ。こういう書き方もあるという紹介だ。
[java] 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引数はファンクタ指定
}
[/java]

幅指定文字列変換（難易度：★★☆☆☆）

問題

int 型の値、文字幅を引数で受け取って、それを文字列に変換したものを返す string itostr(int a, int wd) を定義しなさい。
単純に文字列化したものの文字数が wd 未満の場合は、先頭に半角空白（’ ‘）を付加し、文字数がwdになるようにしなさい。

例えば、123, 4 が引数で渡された場合は ” 123″ を、-99, 2 が渡された場合は “-99” を返す。
[java] #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;
}
[/java]

ヒント

・数値を文字列に変換するには to_string(int) を使うといいぞ。
・文字列長を取得するには size() を使う。
・文字列を連結するには + 演算子を使うぞ。

解答例

[java] string itostr(int a, int wd) {
auto txt = to_string(a); // 引数の値を文字列に変換
while( txt.size() < wd ) // 文字幅が足りない場合は
txt = ‘ ‘ + txt; // 先頭に半角空白を付加
return txt;
}
[/java]

解説

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個）。
[java] #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;
}
[/java]

ヒント

・文字列を昇順カウントするには std::map<string, int> 型の mp を使うといいぞ。
・各文字列をカウントするには mp[文字列] += 1; とすればいいぞ。
・拡張for文で順に要素をアクセスすると、昇順に要素を取り出すことがで

解答例

[java] 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 は昇順にソートされて
[/java]

解説

文字列を昇順カウントするには std::map<string, int> 型の mp を使うとよい。各文字列の出現数をカウントするには、単に mp[文字列] += 1; とするとよい（mp[文字列] は自動的に0に初期化される）。 map の要素は自動的に昇順ソートされているので、拡張for文で順に要素をアクセスすると、文字列数を順に取り出すことができる。