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

TsudaNobuhide

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

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

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

配列充填（難易度：★★☆☆☆）

問題

int[] 型のar, 要素数sz, データdを受け取り、ar から sz個の要素にdを充填する関数 void my_fill(int ar[], int sz, int d) を実装しなさい。

例えば、int v[] = {0, 0, 0, 0, 0, 0, 0} のとき、my_fill(v+2, 3, 1) がコールされると、 v は {0, 0, 1, 1, 1, 0, 0} となる。
[java] #include <iostream>
#include <algorithm>
#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_fill(int ar[], int sz, int d) {
// ToDo: 標準ライブラリの関数を使い、サイズ sz の配列 ar のすべての要素を d にする
}
int main()
{
int ar[] = {0, 0, 0, 0, 0, 0, 0}; // 要素数：7
const int sz = sizeof(ar)/sizeof(int);
my_fill(ar+2, 3, 1);
DO_TEST( vector<int>(ar, ar+sz) == vector<int>({0, 0, 1, 1, 1, 0, 0}) );
my_fill(ar, 7, 2);
DO_TEST( vector<int>(ar, ar+sz) == vector<int>({2, 2, 2, 2, 2, 2, 2}) );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・コンテナクラスの全要素を設定するには、void std::fill(first, last, value) 関数を使うんだぞ。
・first, last は要素を設定する範囲、value は設定する値だぞ。

解答例

[java] void my_fill(int ar[], int sz, int d) {
fill(ar, ar + sz, d); // 範囲 [ar, ar + sz) の値を d に設定
}
[/java]

解説

コンテナクラスの全要素を設定するには、std::fill(first, last, value) 関数を使う。 first, last は充填範囲の先頭, 末尾+1で、配列アドレスまたはイテレータを指定可能だぞ。

重複除去ソート（難易度：★★★☆☆）

問題

vector<string>>参照型のlstを引数で受け取り、重複する要素を削除し、さらに小さい順にソートする関数 void uniqSort(vector<string>& lst) を実装しなさい。

例えば、{“abc”, “abb”, “abc”} が渡された場合は、”abc” が重複しているのでひとつ消され、昇順ソートされた {“abb”, “abc”} を返す。
[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 uniqSort(vector<string>& lst) {
// ToDo: 標準ライブラリの関数を使い、lst の重複する要素を削除・昇順ソートする
}
int main() {
vector<string> vs = {"abc", "xz", "ab", "ac", "abb", "xyz", "ab", "abc", "xz"};
uniqSort(vs);
DO_TEST(vs == vector<string>({"ab", "abb", "abc", "ac", "xyz", "xz"}));
vector<string> vs2 = {"abc", "abc", "abc"};
uniqSort(vs2);
DO_TEST(vs2 == vector<string>({"abc"}));
vector<string> vs3 = {};
uniqSort(vs3);
DO_TEST(vs3 == vector<string>());
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・問題では重複を削除してからソートと書いているが、先にソート処理を行うぞ。
・昇順ソート処理は std::sort(first, last) を使うんだぞ。
・重複を除去するには std::unique(first, last) を使うんだぞ。

解答例

[java] void uniqSort(vector<string>& lst) {
sort(lst.begin(), lst.end()); // 要素を昇順ソート
auto itr = unique(lst.begin(), lst.end()); // 重複要素を削除
lst.resize(itr – lst.begin()); // 不要な要素を削除
}
[/java]

解説

問題では重複を削除してからソートと書いているが、先にソート処理を行う。
昇順ソートは std::sort(first, last) を使う。first, last は言うまでもないが、ソート範囲だ。コンテナ全体をソートするので、lst.first(), lst.end() を渡すんだぞ。
最後に std::unique(first, last) をコールして重複した要素を削除する。この関数も std::remove(first, last) 同様にコンテナの要素そのものを削除せず、前にデータを詰めて、最後のデータ+1を指すイテレータを返すので、lst.resize(itr – lst.begin()); で、不要な要素を削除しているぞ。

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

問題

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

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

“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 permutation(string str, vector<string>& lst)
{
// ToDo: 標準ライブラリの関数を使い、昇順に順列をすべて生成し、lst に格納する
}
int main() {
vector<string> lst;
permutation("abc", lst);
DO_TEST( lst == vector<string>({"abc", "acb", "bac", "bca", "cab", "cba"}) );
permutation("cba", lst);
DO_TEST( lst == vector<string>({"abc", "acb", "bac", "bca", "cab", "cba"}) );
permutation("aba", lst);
DO_TEST( lst == vector<string>({"aab", "aba", "baa"}) );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・順列を生成するには、 next_permutation(first, last) 関数を使うんだぞ。

解答例

[java] void permutation(string str, vector<string>& lst)
{
lst.clear(); // lst クリア
sort(str.begin(), str.end()); // 全順列が生成されるように、str の各文字をソート
do {
lst.push_back(str); // 生成された順列テキストを lst に保存
} while (next_permutation(str.begin(), str.end())); // 次の順列を生成
}
[/java]

解説

文字列の順列を生成するには next_permutation(str.begin(), str.end()) を用いる。
結果文字列は昇順に生成されるので、最初に文字列の各文字をソートしておく。
lst は最初に内容をクリアし、生成された順列文字列を push_back() で追加していく。