Help us understand the problem. What is going on with this article?

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

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

はじめに

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

boost::irange

ABC072B - OddString

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

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 - 数式の書き換え

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)

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 - スペース高橋君

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 - ムーアの法則

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.firstr.secondで得られます。

まとめ

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

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

Lily0727K
東大医学部卒、血液内科専門医です。令和元年にソフトウェアエンジニアに転職しました!競技プログラミングはPythonとC++でAtCoder青色。ポーカーのGTO戦略を研究して、noteに記事を書いています。
https://note.mu/nekochan0214
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした