【分野別　初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【二分探索】

[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa)の`2-3. 分野別　初中級者が解くべき過去問精選 100 問`を初級者がC++で解いていきます。

# 二分探索

## [18　ALDS_4_B - 二分探索](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja)
AIZU ONLINE JUDGE に登録していないので、後回し。

## [19　JOI 2009 本選 2 - ピザ](https://atcoder.jp/contests/joi2009ho/tasks/joi2009ho_b)
習った通りにlower_boundを使って配達先に近い店舗を探すだけ。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define repeq(i, a, b) for (ll i = a; i <= b; i++)
#define rrep(i, b, a) for (ll i = b; i >= a; i--)
#define repb(i, n) for (ll i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  ll d, n, m;
  cin >> d >> n >> m;
  vector<ll> a(n + 1, 0);
  rep(i, 1, n) cin >> a.at(i);
  
  a.at(n) = d;
  sort(a.begin(), a.end());
  ll res = 0;
  rep(i, 0, m) {
    ll k;
    cin >> k;
    
    int it = lower_bound(a.begin(), a.end(), k) - a.begin();
    ll tmp = abs(a.at(it) - k);
    if (it > 0) tmp = min(tmp, abs(a.at(it - 1) - k));
    res += tmp;
  }
  cout << res << endl;
}
```
https://atcoder.jp/contests/joi2009ho/submissions/38094260

## [20　AtCoder Beginner Contest 077 C - Snuke Festival](https://atcoder.jp/contests/abc077/tasks/arc084_a)
三重ループは間に合わないので中部を固定して、条件に当てはまる上部と下部の数を数える。それさえ思いつけば、あとは数えるときにlower_boundとupper_boundを使えばよい。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N;
  cin >> N;
  
  vector<ll> A(N), B(N), C(N);
  rep(i, 0, N) cin >> A.at(i);
  rep(i, 0, N) cin >> B.at(i);
  rep(i, 0, N) cin >> C.at(i);
  
  sort(all(A));
  sort(all(B));
  sort(all(C));
  
  ll ans = 0;
  fore(b, B) {
    ll a = lower_bound(all(A), b) - A.begin();
    ll c = N - (upper_bound(all(C), b) - C.begin());
    ans += a * c;
  }
  cout << ans << endl;
}
```
https://atcoder.jp/contests/abc077/submissions/38110439

## [21　AtCoder Beginner Contest 023 D - 射撃王](https://atcoder.jp/contests/abc023/tasks/abc023_d)
二分探索というか二分法。全く分からなくて[こちら](https://drken1215.hatenablog.com/entry/2021/06/12/113100)にお世話になった。え、これみんな思いつくの？どうやって思いつくの？
とも思ったけれど、何のために二分探索(二分法)するのか考えれば分かるはず。
ちなみに、[こちらの記事](https://qiita.com/drken/items/97e37dd6143e33a64c8c)にも非常にお世話になった。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N;
  cin >> N;
  vector<long long> H(N), S(N);
  rep(i, 0, N) cin >> H.at(i) >> S.at(i);
  
  ll left = 0, right = inf;
  while(right - left > 1) {
    ll mid = (right + left) / 2;
    bool is_ok = true;
    
    vector<ll> T(N);
    rep(i, 0, N) {
      if (mid < H.at(i)) is_ok = false;
      else T.at(i) = (mid - H.at(i)) / S.at(i);
    }
    sort(all(T));
    
    rep(i, 0, N) {
      if (T.at(i) < i) is_ok = false;
    }
    
    if (is_ok) right = mid;
    else left = mid;
  }
  cout << right << endl;
}
```
https://atcoder.jp/contests/abc023/submissions/38113031

## [22　AtCoder Regular Contest 054 B - ムーアの法則](https://atcoder.jp/contests/arc054/tasks/arc054_b)
> 微分して二分法をすると解けます

と元記事に書いてあるのを先に見てしまったので解けてしまった。微分してf'(x)が0になるところを二分法で探す。三分法はまだ調べていない。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

double fd(double x, double P) {
  return 1.0 + P * log(pow(2.0, (-2.0 / 3.0))) * (pow(2.0, (- x / 1.5)));
}

int main() {
  double P;
  cin >> P;
  
  double left = - inf, right = inf;
    while (right - left > 0.0000000001) {
      double mid = (left + right) / 2;
      if (fd(mid, P) == 0) break;
      else if (fd(mid, P) < 0) left = mid;
      else right = mid;
    }
  
  double ans;
  if (right > 0) ans = right + P / (pow(2.0, 2.0 / 3.0 * right));
  else ans = P;
  
  cout << fixed << setprecision(10);
  cout << ans << endl;
}
```
https://atcoder.jp/contests/arc054/submissions/38128540

そもそもf'(x) = 0になるxを普通に計算すればよいのでは？と思ったんですが、合ってますか？
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  double P;
  cin >> P;
  
  double x = log(-1.0 / (P * log(pow(2.0, (-2.0/3.0))))) / log(pow(2.0, (-2.0/3.0)));
  
  double ans;
  if (x > 0) ans = x + P / (pow(2.0, 2.0 / 3.0 * x));
  else ans = P;
  
  cout << fixed << setprecision(10);
  cout << ans << endl;
}
```
https://atcoder.jp/contests/arc054/submissions/38127795

## [23　JOI 2008 本選 3 - ダーツ](https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6)
思いつかなかった。[こちら](https://qiita.com/e869120/items/25cb52ba47be0fd418d6#5-%E3%81%AF%E3%82%84%E3%81%84%E6%8E%A2%E7%B4%A2%E6%B3%95%E5%8D%8A%E5%88%86%E5%85%A8%E5%88%97%E6%8C%99)で半分全列挙について触れられているのに読んでいなかった。問題を読む前にアルゴリズムの解説記事はちゃんと読もう。
```c++
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> P(N);
  rep(i, 0, N) cin >> P.at(i);
  P.push_back(0);
  
  vector<int> S;
  rep(i, 0, N + 1) {
    rep(j, 0, N + 1) {
      S.push_back(P.at(i) + P.at(j));
    }
  }
  sort(all(S));
  
  int ans = 0;
  fore(s, S) {
    int it = lower_bound(all(S), M - s) - S.begin();
    if (it == 0) continue;
    ans = max(ans, s + S.at(it - 1));
  }
  cout << ans << endl;
}
```
https://atcoder.jp/contests/joi2008ho/submissions/38293084