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

TsudaNobuhide

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

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

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

配列ソート（難易度：★★☆☆☆）

問題

int[] 型のar, 要素数szを受け取り、要素を昇順にソートする関数 void sortArray(int ar[], int sz) を実装しなさい。

例えば、{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5} が渡された場合は、結果は {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9} となる。
[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 sortArray(int ar[], int sz) {
// ToDo: 標準ライブラリの関数を使って、サイズ sz の配列 ar をソートする
}
int main()
{
int ar0[] = {123};
const int sz0 = sizeof(ar0)/sizeof(int);
sortArray(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);
sortArray(ar, sz);
DO_TEST( vector<int>(ar, ar+sz) == vector<int>({1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}) );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・配列要素を昇順にソートするには、 sort(first, last) 関数を使うんだぞ。
・first, last はソート範囲を示すポインタだぞ。

解答例

[java] void sortArray(int ar[], int sz) {
sort(ar, ar+sz); // サイズ sz の配列 ar をソート
}
[/java]

解説

sort(first, last) 関数を使うと、データを簡単に昇順ソートすることができる。
使い方は簡単で、第1・2引数に配列アドレス・配列末尾アドレス+1を渡すだけだ。
配列末尾アドレス+1は配列先頭アドレス+要素数で計算できるぞ。
または、sort(&ar[0], &ar[sz]); と書いてもいいぞ。

リバース（難易度：★★☆☆☆）

問題

引数で渡された文字列strの文字順序を逆転した文字列を返す関数 string my_reverse(const string &str) を実装しなさい。

例えば、my_reverse(“abcxyz”) は “zyxcba” を返す。
[java] #include <iostream>
#include <algorithm>
#include <string>
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);
}
string my_reverse(const string& str) {
return ""; // ToDo: 標準ライブラリの関数を使い、str を反転した文字列を返すようにする
}
int main()
{
DO_TEST( my_reverse("") == "" );
DO_TEST( my_reverse("a") == "a" );
DO_TEST( my_reverse("abc") == "cba" );
DO_TEST( my_reverse("abcd") == "dcba" );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・コンテナクラスの要素を逆順にするには、void std::reverse(first, last) 関数を使うんだぞ。
・first, last は逆順にする範囲を示すイテレータだぞ。
・引数は const オブジェクトで変更不可なので、いったん別の変数にコピーする必要があるぞ。

解答例

[java] string my_reverse(const string& str) {
string s = str; // 作業用文字列にコピー
reverse(s.begin(), s.end()); // s の文字を順序反転
return s;
}
[/java]

解説

コンテナクラスの要素を逆順にするには、 reverse(first, last) 関数を使う。解答例の reverse() 関数は、引数が const string& で、string を返すので、最初に作業用文字列にコピーし、標準関数の reverse(first, last) をコールして要素順序を反転させ、作業用文字列を値として返す。

ローテイト（難易度：★★☆☆☆）

問題

文字列str、ローテイトする文字数Nを引数で渡され、strを左にN文字ローテイトしたものを返す関数 string my_rotate(string str, int N) を実装しなさい。

例えば、my_rotate(“abcxyz”, 2) は “cxyzab” を返す。
[java] #include <iostream>
#include <algorithm>
#include <string>
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);
}
string my_rotate(const string& str, int n) {
return ""; // ToDo: 標準ライブラリの関数を使い、str をn文字左にローテイトした文字列を返す
}
int main()
{
DO_TEST( my_rotate("", 0) == "" );
DO_TEST( my_rotate("abc", 0) == "abc" );
DO_TEST( my_rotate("abc", 1) == "bca" );
DO_TEST( my_rotate("abc", 2) == "cab");
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・コンテナクラスの要素をローテイトするには、void std::rotate(first, middle, last) 関数を使うんだぞ。
・first, last は逆順にする範囲を示すイテレータだぞ。
・middle はどの位置の要素を先頭に移動するかを示すイテレータだぞ。
・引数は const オブジェクトで変更不可なので、いったん別の変数にコピーする必要があるぞ。

解答例

[java] string my_rotate(const string& str, int n) {
if( n < 0 || n >= str.size() ) return str; // 範囲チェック
string s = str; // 作業用文字列にコピー
rotate(s.begin(), s.begin() + n, s.end()); // s をn文字ローテイト
return s;
}
[/java]

解説

コンテナの要素をローテイトするには rotate(first, middle, last) 関数を使う。 first, last はコンテナの先頭, 末尾+1だ。そして middle はローテイト後の先頭になるデータ位置を示す。
例えば、v が vector の場合は「rotate(v.begin(), v.begin()+n, v.end())」をコールすると、左にn個だけローテイトされるぞ。