競技プログラミングで使えるBoostライブラリ　初級編

#競技プログラミングで使えるBoostライブラリ　初級編

###はじめに

AtCoderではC++の`Boost`ライブラリを使用することができます。
`Boost`ライブラリには非常に多くの機能がありますが、そのうち便利だなと思ったものを簡単に紹介します。

###boost::irange

[ABC072B - OddString](https://atcoder.jp/contests/abc072/tasks/abc072_b)

```c++:ABC072B
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;

int main() {
  string s;
  cin >> s;
  int n = s.size();
  for (int i : irange(0, n, 2)) {
    cout << s[i];
  }
  cout << endl;
}
```

整数のレンジを使うには`boost::irange`関数を使います。
範囲として`[0, n)`を指定して、第3引数でステップ幅を`2`に指定しています。
(第3引数を省略するとステップ幅は`1`になります)
これに対してrange-based for文を記述することができ、Pythonのfor文と近い感覚になります。

###boost::multiprecision::cpp_int

[ABC059B - Comparison](https://atcoder.jp/contests/abc059/tasks/abc059_b)

```c++:ABC059B
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

int main() {
  cpp_int a, b;
  cin >> a >> b;
  cout << (a > b ? "GREATER" : (a == b ? "EQUAL" : "LESS")) << endl;
}
```

多倍長整数を扱うには`boost::multiprecision::cpp_int`を使います。
この問題で与えられる整数は$10^{100}$以下という制限となっており、数値として扱うために多倍長整数で受け取っています。

###boost::algorithm::split

[ABC033C - 数式の書き換え](https://atcoder.jp/contests/abc033/tasks/abc033_c)

```c++:ABC033C.cpp
#include <bits/stdc++.h>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>

using namespace std;
using boost::algorithm::split;

int main() {
  string s;
  cin >> s;
  vector<string> plus_split_s;
  split(plus_split_s, s, boost::is_any_of("+"));
  int cnt = 0;
  for (const string& elem : plus_split_s) {
    if (elem.find('0') == string::npos) ++cnt;
  }
  cout << cnt << endl;
}
```

指定した区切り文字で文字列を分割するには`boost::algorithm::split`関数を使用します。
得られた結果は指定したコンテナで受け取ります。
区切り文字かどうかを判定する述語として`boost::is_any_of`を使用しています。
今回の例では文字列を`+`で区切っています。以下のように記述してもよいです。
`split(plus_split_s, s, [](char c){return c == '+';});`

###boost::algorithm::join

[ABC042B - 文字列大好きいろはちゃんイージー / Iroha Loves Strings (ABC Edition)](https://atcoder.jp/contests/abc042/tasks/abc042_b)

```c++:ABC042B.cpp
#include <bits/stdc++.h>
#include <boost/algorithm/string/join.hpp>

using namespace std; 
using boost::algorithm::join;

int main() {
  int n, l;
  cin >> n >> l;
  vector<string> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }
  sort(arr.begin(), arr.end());
  string s = join(arr, "");
  cout << s << endl;
}
```

コンテナの文字列をつなげて一つの文字列にするには、`boost::algorithm::join`関数を使用します。
つなげる区切り文字を指定でき、例えば以下のように記述すれば`_`で区切られた文字列になります。
`string s = join(arr, "_");`

###boost::algorithm::replace_all

[ARC045A - スペース高橋君](https://atcoder.jp/contests/arc045/tasks/arc045_a)

```c++:ARC45.cpp
#include <bits/stdc++.h>
#include <boost/algorithm/string/replace.hpp>

using namespace std;
using boost::algorithm::replace_all;

int main() {
  string s;
  getline(cin, s);
  replace_all(s, "Left", "<");
  replace_all(s, "Right", ">");
  replace_all(s, "AtCoder", "A");
  cout << s << endl;
}
```

文字列の中の要素をすべて別の要素に置き換えるには`boost::algorithm::replace_all`関数を使用します。
これは破壊的処理であり、もともとの文字列`s`を変更しています。
非破壊的にコピーを作って置換する場合は`boost::algorithm::replace_all_copy`関数を使えばよいです。
例えば以下のように書きます。
`string result = boost::algorithm::replace_all_copy(s, "AtCoder", "A");`

###boost::math:: tools::brent_find_minima

[ARC54B - ムーアの法則](https://atcoder.jp/contests/arc054/tasks/arc054_b)

```c++:ARC54B.cpp
#include <bits/stdc++.h>
#include <boost/math/tools/minima.hpp>
 
using namespace std;
using boost::math::tools::brent_find_minima;
 
int main() {
  double p;
  cin >> p;
  auto r = brent_find_minima([p](double x) {return x + p / pow(2.0 , x / 1.5);}, 0.0, 100.0, 30);
  cout << fixed << setprecision(15);
  cout << r.second << endl;
}
```

関数の最小値を探索するには`boost::math::tools::brent_find_minima`関数を使用します。
今回の例では関数をラムダ式で記述し、`x`の探索範囲を指定しています。
結果を`r`に代入しています。最小値となる`x`の値と関数の値が、それぞれ`r.first`と`r.second`で得られます。

###まとめ

いかがだったでしょうか。
競技プログラミングの問題を例として、`Boost`ライブラリの便利な機能の一部を紹介できたかなと思います。

もっと便利な書き方もあるよ、などのコメントもいただけると嬉しいです！