LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@Parascorpaena

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

Last updated at Posted at 2023-01-18

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

二分探索

18　ALDS_4_B - 二分探索

AIZU ONLINE JUDGE に登録していないので、後回し。

19　JOI 2009 本選 2 - ピザ

習った通りにlower_boundを使って配達先に近い店舗を探すだけ。

#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;
}

20　AtCoder Beginner Contest 077 C - Snuke Festival

三重ループは間に合わないので中部を固定して、条件に当てはまる上部と下部の数を数える。それさえ思いつけば、あとは数えるときにlower_boundとupper_boundを使えばよい。

#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;
}

21　AtCoder Beginner Contest 023 D - 射撃王

二分探索というか二分法。全く分からなくてこちらにお世話になった。え、これみんな思いつくの？どうやって思いつくの？
とも思ったけれど、何のために二分探索(二分法)するのか考えれば分かるはず。
ちなみに、こちらの記事にも非常にお世話になった。

#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;
}

22　AtCoder Regular Contest 054 B - ムーアの法則

微分して二分法をすると解けます

と元記事に書いてあるのを先に見てしまったので解けてしまった。微分してf'(x)が0になるところを二分法で探す。三分法はまだ調べていない。

#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;
}

そもそもf'(x) = 0になるxを普通に計算すればよいのでは？と思ったんですが、合ってますか？

#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;
}

23　JOI 2008 本選 3 - ダーツ

思いつかなかった。こちらで半分全列挙について触れられているのに読んでいなかった。問題を読む前にアルゴリズムの解説記事はちゃんと読もう。

#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;
}

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?