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

これまでに競技プログラミング風標準C++ライブラリ入門を2シーズン、8回にわたりお届けしたが、各方面に好評だったので、さらにおかわり（シーズン3）として【第9回】～【第12回】をお届けする。

標準C++ライブラリを知っていれば比較的簡単な問題をたくさん解いて、標準C++ライブラリに親しんでいただこうというのが本連載の趣旨だ。

各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ（ideonなど）で保存・ビルド・実行し、 NGが出ないようにテストコードの「ToDo:」部分のコードを完成させてほしい。

「ヒント」「解答例」「解説」はデフォルトでは非表示になっており、中身を読みたい場合は【show】ボタンを押せば表示される。これらをすぐに読むのではなく、ちゃんと解答を考え、使用する標準ライブラりのクラス・関数をweb検索して勉強し、コード記述・ビルド・実行してからそれらを読むのを強く推奨する。なにごとも自分で考え、いろいろ試した上で、解答などを見るようにするのが肝要だ。その方が解答が印象に残り問題解決方法が記憶に定着しやすいのだ。

ソート済み？（難易度：★☆☆☆☆）

問題

引数で、配列アドレス・要素数を受け取り、配列要素が昇順にソート済みかどうかを判定する関数 bool my_is_sorted(const int ar[], int sz) を実装しなさい。

例えば、ar[]: {1, 1, 2, 5, 100}、sz: 5 が渡された場合は true を、ar[]: {1, 5, 2, 1, 100}、sz: 5 が渡された場合は false を返す。
[java] #include <iostream> // 標準入出力ライブラリ
#include <algorithm>
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);
}
bool my_is_sorted(const int ar[], int sz) { // ar: 配列アドレス、sz: 要素数
return true; // ToDo: 標準関数を使い、ここを書き換えて、ar[] の要素が昇順ソート済みかどうかを返す
}
int main() {
const int ar1[] = {1, 1, 2, 5, 100};
const int SZ1 = sizeof(ar1, sizeof(int));
DO_TEST( my_is_sorted(ar1, SZ1) );
const int ar2[] = {1, 5, 2, 1, 100};
const int SZ2 = sizeof(ar2, sizeof(int));
DO_TEST( !my_is_sorted(ar2, SZ2) );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・指定範囲が昇順ソート済みかどうかを判定するには std::is_sorted(first, last) を使うぞ。
・first, last は範囲の最初, 最後の要素+1 だぞ。

解答例

[java] bool my_is_sorted(const int ar[], int sz) { // ar: 配列アドレス、sz: 要素数
return is_sorted(ar, ar + sz); // [ar, ar+sz) がソート済みか？
}
[/java]

解説

指定範囲が昇順ソート済みかどうかを判定するには std::is_sorted(first, last) を使うだけだ。本問題では配列要素を判定するので、is_sorted(ar, ar+sz) を呼ぶだけだ。

ちなみに、第3引数で要素の順序を判定する関数オブジェクトを指定可能なので、 is_sorted(ar, ar+sz, std::greater()) とすれば、指定範囲が降順ソートされているかどうかを判定できるぞ。

複素数角度（難易度：★☆☆☆☆）

問題

X軸方向が実数、Y軸方向が虚数の複素平面上で、引数で与えられた複素数と原点を結んだ直線とX軸との角度（反時計回りがプラス）を返す関数 int angle(const complex<double>& c) を実装しなさい。
なお、角度の単位は度（degree）とする。

例えば、実数1, 虚数1 が与えられた場合は 45 を返す。
[java] #include <iostream> // 標準入出力ライブラリ
#include <complex>
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);
}
#define PI 3.1415926535
int angle(const complex<double>& c) {
return 0; // ToDo: 標準ライブラリの関数を使い、複素数cのX軸からの角度を返す
}
int main() {
DO_TEST( angle(complex<double>(1, 0)) == 0 );
DO_TEST( angle(complex<double>(0, 1)) == 90 );
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・複素平面上で、与えられた複素数と原点を結んだ直線とX軸との角度を求めるには T std::arg<T>(const complex<T>&) を使うぞ。
・std::arg(c) はラジアンを返すが、本問題では度（degree）での値を返す必要があるので、変換が必要だぞ。

解答例

[java] int angle(const complex<double>& c) {
return (int)(arg<double>(c) * 180 / PI); // arg() で角度（ラジアン）を求め、度（degree）に変換
}
[/java]

解説

複素数cのX軸からの角度を求めるには T std::arg<T>(const complex<T>&) を使う。 T は複素数要素の型で、本問題の場合は double だ。
std::arg() の返す値の単位はラジアンで、本問題では度（degree）を返すという仕様なので、返値に *180/PI を適用させて、度に変換している。

内積（難易度：★☆☆☆☆）

問題

const vector<int>& 型の引数 v1, v2 の2つを受け取り、それらの内積（Σv1[i]*v2[i]）を返す関数 int my_inner_product(const vector<int>& v1, const vector<int>& v2) を実装しなさい。

ただし、v1, v2 のサイズが異なる場合は、小さい方のサイズ分の内積を計算するものとする。
[java] #include <iostream> // 標準入出力ライブラリ
#include <numeric>
#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 my_inner_product(const vector<int>& v1, const vector<int>& v2) {
return 0; // ToDo: 標準関数を使い、ここを書き換えて、v1 と v2 の内積を返す
}
int main() {
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {7, 4, 3};
DO_TEST( my_inner_product(v1, v2) == 24 );
v1 = { 1, 2, 3, 4 };
v2 = { 7, 6 };
DO_TEST(my_inner_product(v1, v2) == 19);
cout << "\nGood Job!\n";
return 0;
}
[/java]

ヒント

・内積を計算するには、std::inner_product(first1, last1, first2, init) を使うんだぞ。
・first1, last1 は内積を計算する片方の範囲、first2 はもう片方の最初だぞ。
・init は初期値で、通常0を指定するぞ。

解答例

[java] int my_inner_product(const vector<int>& v1, const vector<int>& v2) {
int sz = min(v1.size(), v2.size()); // 小さい方のサイズに合わせる
return inner_product(v1.begin(), v1.begin() + sz, v2.begin(), 0); // 内積計算
}
[/java]

解説

内積を計算するには、std::inner_product(first1, last1, first2, init) を使う。 first1, last1 は内積を計算する片方の範囲で、first2 はもう片方の先頭（イテレータまたはアドレス）だ。本問題の場合は、コンテナクラスが渡されるので、イテレータの begin(), end() を使う。
v1, v2 のサイズが異なる場合は、小さい方のサイズに合わせるという仕様なので、それぞれのサイズの小さい方を sz に設定し、 v1.begin(), v1.begin() + sz で範囲を指定している。残りの引数は v2.begin() と初期値に 0 を指定している。