AtCoder が提供しているABC（AtCoder Beginner Contest）077 C問題をC++で解いてみました。ABC077は、2017年11月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Snuke Festival（Difficulty : 1096）
問題の詳細は、リンク先をご覧ください。
中部のパーツを固定して、上下のパーツ数を二分探索で調べます。AtCoder Problems による Difficulty は 1096 でした。
解答案
C++ の二分探索を行う lower_bound、upper_bound の動作についてまとめます。
| 求めたい要素数 | コード |
| x 未満の配列 a の要素数 | lower_bound(a.begin(), a.end(), x) - a.begin() |
| x 以下の配列 a の要素数 | upper_bound(a.begin(), a.end(), x) - a.begin() |
| x を超える配列 a の要素数 | a.end() - upper_bound(a.begin(), a.end(), x); |
| x 以上の配列 a の要素数 | a.end() - lower_bound(a.begin(), a.end(), x); |
C++ プログラム例（ABC077C）
上部の配列 a と下部の配列 c を読み込み、それぞれソートします（14、23行目）。
中部のパーツを1つ選び、そのパーツより小さい上部のパーツ数（diff1）と大きい下部のパーツ数（diff2）を求め、積を result に加えます（25ー30行目）。
最後に result を出力します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
vector<int> b(n);
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
sort(c.begin(), c.end());
ll result = 0;
for (int i = 0; i < n; ++i) {
ll diff1 = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
ll diff2 = c.end() - upper_bound(c.begin(), c.end(), b[i]);
result += diff1 * diff2;
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
値の二分探索についてまとめました。
引き続き ABC の問題を紹介していきます。
