はじめに
皆さんこんにちは！
二分探索の基礎はできるから、応用問題を頑張るぞい！
精選100問はこちら！
18 ALDS_4_B - 二分探索
問題はこちらです！
問題文↓
main配列とsub配列が与えられるので、sub配列の要素がmain配列にいくつ含まれるかをカウントしてください
個数が大きいので、2分探索しましょうという問題ですね！
以下のようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n; cin >> n; vector<int> A(n); rep(i, n) cin >> A[i]; int m; cin >> m; int ans = 0; rep(i, m) { int x; cin >> x; if (x == A[lower_bound(all(A), x) - A.begin()]) ans++; } cout << ans << endl; return 0; }
STLにはlower_boundがあるので、それを活用しましょう！
19 JOI 2009 本選 2 - ピザ
問題はこちらです！
問題文↓
ピザ屋と宅配先は円状に並んでいる いくつかのピザ屋と宅配先の座標が与えられるので一番近いピザ屋からピザを届けて、最も小さいコストでピザを配達してください コストは、距離とします
宅配先から一番近いピザ屋をコーナーケースに注意しながら二分探索していけばいいですね！
宅配先が0のときと、一番遠い場所のピザ屋よりも奥のときには注意です
宅配先が0のときはコストが必ず0になり、一番遠い場所のピザ屋よりも奥のときは0とも比較しないといけません
以下のようになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { // input. ll d, n, m; cin >> d >> n >> m; vector<ll> D(n, 0); vector<ll> K(m); rep(i, n - 1) cin >> D[i + 1]; // はじめは0(本店がある). rep(i, m) cin >> K[i]; // 二分探索をするので、前処理(ソート+同じ座標の削除). sort(all(D)); sort(all(K)); D.erase(unique(all(D)), D.end()); ll ans = 0; rep(i, m) { if (K[i] == 0) // もし0へ配達するなら. { // 本店から運ぶのてコスト0. ans += 0; } else if (K[i] > D.back()) // もし、一番大きい座標のピザ屋よりも先の宅配先なら、0と一番大きい座標の比較 { ans += min((d - K[i]), (K[i] - D.back())); } else { ans += min(K[i] - D[lower_bound(all(D), K[i]) - D.begin() - 1], D[lower_bound(all(D), K[i]) - D.begin()] - K[i]); } } cout << ans << endl; return 0; }
同じ座標の削除は必要なのだろうか、、、？
20 AtCoder Beginner Contest 077 C - Snuke Festival
問題はこちらです！
問題文↓
3つのアイテムを選んで順番に並べさせたとき、階段状に大きくなるようにしたい 選び方は何通りあるか ただし、個数はとても多いものとする
真ん中のアイテムを固定すると、上と下のアイテムの個数がわかります！
このような感じになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { // 入力. ll n; cin >> n; vector<ll> A(n), B(n), C(n); rep(i, n) cin >> A[i]; rep(i, n) cin >> B[i]; rep(i, n) cin >> C[i]; // 二分探索するのでソート. sort(all(A)); sort(all(B)); sort(all(C)); // 真ん中のアイテムを全探索して、上には小さいアイテム、下には大きいアイテムの個数を数える. ll ans = 0; rep(i, n) { ll top = (lower_bound(all(A), B[i]) - A.begin()); ll bottom = (n - (upper_bound(all(C), B[i]) - C.begin())); ans += top * bottom; } cout << ans << endl; return 0; }
二分探索って気づいたら簡単ですね
21 AtCoder Beginner Contest 023 D - 射撃王
問題はこちらです！
問題文↓
いくつかの風船が飛んでおり、これらを全て撃ち抜く 撃ち抜いた風船の高度がコストとなる 風船のはじめの高度と毎秒の速度が与えられるので、コストをできる限り最低にしたい この最小値を求めてください
全ての風船を高度x以内に消すことが出来るかを考えると二分探索をすれば良いことがわかる！
コードはこんな感じになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { // 入力. ll n; cin >> n; vector<pair<ll, ll>> Balloons(n); rep(i, n) cin >> Balloons[i].first >> Balloons[i].second; // 二分探索をする. ll left = 0, right = INT64_MAX; while (right > left + 1) { ll x = (left + right) / 2; // 全ての風船が高さxで破壊しきることが可能か. bool f = true; vector<ll> times; rep(i, n) { if (Balloons[i].first > x) { // もし風船の初期高度がxを超えていたらアウト. f = false; } else { // 何秒まで破壊しなくてもいいか. times.push_back((x - Balloons[i].first) / Balloons[i].second); } } // 破壊しなくては行けない順番にソート. sort(all(times)); rep(i, times.size()) { if (times[i] < i) f = false; } if (f) right = x; else left = x; } // 結果を出力する. cout << right << endl; return 0; }
22 AtCoder Regular Contest 054 B - ムーアの法則
問題はこちらです！
問題文↓
ある現代のコンピュータではp年かかる計算があります
1年おきにコンピュータの計算の速さが{2}^{x/1.5}倍になるという法則に従えば、一番短くて何年で実行を終わることができますか？
もちろん計算中にコンピュータを変えることはできないです
これは、めちゃくちゃいい問題でした！
まずは立式するところから始めます
仕事のスピードが速くなる=反比例となるって考えれば、x年後にy年かかるという式は以下になります
$f(x)=\frac{1}{{2}^{\frac{x}{1.5}}}a+x$
グラフを書くとこんな感じ...
いい感じな下に凸のグラフなので、これの最小値を求めます！
最小値を求めるには式を微分して、0を代入して解くといった感じですね
微分はwolfram君にでも投げましょう
すると、以下のように帰ってきました
$f'(x)=1-\frac{1}{3}a \times 2^{1-x} \times \sqrt[3]{{2}^{x}} \times log(2)$(ここでのlogの底はe)
これに$f'(x)=0$となるようにxを解くのが極小となる
xを解くと、$x=\frac{3(log(2)-log(\frac{3}{a log(2)}))}{2log(2)}$となる！
グラフはこんな感じ...
.png)
確かに、極小のx座標になってますね！
あとはこのxをf(x)に代入したら、最小値を求められますね
しかし、x<0のときはそのまま出力することを忘れずに、、、
こんなコードになってO(1)で解けました！
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { ld p; cin >> p; ld x = (3 * (logl(2) - logl(3 / (p * logl(2))))) / (2 * logl(2)); if (x < 0) cout << p << endl; else cout << setprecision(12) << x + 1 / powl(2, 2 * x / 3) * p << endl; return 0; }
微分良いね(手計算とは言っていない)
23 JOI 2008 本選 3 - ダーツ
問題はこちらです！
問題文↓
N個の的があり、ポイントが書かれています 最大4本のダーツを使用して、あたった的の点数の合計があなたの得点です ただし、得点がM点を超えた場合、あなたの得点は0点になります さて、獲得できるポイントの最大は何点でしょう
普通にすると、O(N⁴)かかるので駄目です
しかし、N≦1000なので、O(N²)にすれば間に合いそうです
そこで、半分全列挙をして、いい組み合わせを二分探索で見つけて上げればいいです！
こんな感じのコードになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { // 入力. ll n, m; cin >> n >> m; vector<ll> A(n + 1, 0); rep(i, n) cin >> A[i + 1]; vector<ll> B; rep(i, n + 1) { rep(j, n - i + 1) { B.push_back(A[i] + A[i + j]); } } // 被りを削除. sort(all(B)); B.erase(unique(all(B)), B.end()); // 半分全列挙したもので、二分探索. ll ans = 0; rep(i, B.size()) { if (upper_bound(all(B), m - B[i]) - B.begin() - 1 > -1) ans = max(ans, m - (m - B[i] - B[(upper_bound(all(B), m - B[i]) - B.begin() - 1)])); } cout << ans << endl; return 0; }
だいぶ簡単な問題でした！
終わりに
最後まで読んでくださりありがとうございました
ではまた！
