３章では二分探索がテーマ。まずは一番シンプルな二分探索の問題から。
回答コード
#include <bits/stdc++.h> using namespace std; #define dump(x) cout << #x << " = " << (x) << endl; #define REP(i, n) for (ll i = 0; i < (n); i++) #define ITOC(n) (char)'0' + n #define KETAUNE(keta, num) setw(keta) << setfill('0') << num #define SORTVEC(vec) sort(vec.begin(), vec.end()) #define RSORTVEC(vec) sort(vec.rbegin(), vec.rend()) #define REVERSEVEC(vec) reverse(vec.begin(), vec.end()) #define FOREACH(x, a) for (auto &x : (a)) #define OUT(n) cout << n << endl #define SISHAGONYU(X, base) round(X / (double)base) * base #define KIRISUTE(X, base) X / base *base typedef long long ll; // #include <atcoder/all> // using namespace atcoder; int main() { ll N,X;cin>>N>>X; vector<ll> A(N); REP(i, N) cin>>A[i]; ll L = 0, R = N; while(L<=R) { ll m = (L+R) / 2; if (A[m] == X) { OUT(m+1); return 0; } else if (A[m] < X) { L = m+1; } else { R = m-1; } } }
L=0, R=配列の長さで区間を取り、中間値mを(L+R)/2とする。 A[m] == X: 答え A[m] > X: 目的の値Xより中間値の方が大きいので、R=m-1として右の探索区間を狭める A[m] < X: 目的の値Xより中間値の方が小さいので、L=m+1として左の探索区間を狭める
lower_bound
問題b11ではlower_boundを使うようにというヒントがある。lower_boundのリファレンス を見てみると、「イテレータ範囲[first, last)のうち、指定された要素以上の値が現れる最初の位置のイテレータを取得する。」と書いてある。なるほどさっきの問題もこの関数を丸ごと適用するだけで解けそうだ。b11を解く前に先のa11をlower_boundで解いてみる。
#include <bits/stdc++.h> using namespace std; #define dump(x) cout << #x << " = " << (x) << endl; #define REP(i, n) for (ll i = 0; i < (n); i++) #define ITOC(n) (char)'0' + n #define KETAUNE(keta, num) setw(keta) << setfill('0') << num #define SORTVEC(vec) sort(vec.begin(), vec.end()) #define RSORTVEC(vec) sort(vec.rbegin(), vec.rend()) #define REVERSEVEC(vec) reverse(vec.begin(), vec.end()) #define FOREACH(x, a) for (auto &x : (a)) #define OUT(n) cout << n << endl #define SISHAGONYU(X, base) round(X / (double)base) * base #define KIRISUTE(X, base) X / base *base typedef long long ll; // #include <atcoder/all> // using namespace atcoder; // printf("%.3lf", S); // 小数で割ったあまり fmod(1,1.0) // 末尾3文字 str.substr(str.length() - 3) // 円周率 M_PI // 等差数列の和 // a1: 初項、n: 項数、d: 項差 // return n * (2 * a1 + (n - 1) * d) /2 int main() { ll N,X;cin>>N>>X; vector<ll> A(N); REP(i, N) cin>>A[i]; auto itr = lower_bound(A.begin(), A.end(), X); ll ans = std::distance(A.begin(), itr); OUT(ans+1); }
lower_boundで取って来れるのはイテレータなので、distance関数を使って配列の最初のイテレータとの距離を取ることで添字に変換している。二分探索を自分で書かなくて良いのはなかなか便利。
と、lower_boundの基本的な使い方は分かったところで、問題b11に取り組む。
回答コード
#include <bits/stdc++.h> using namespace std; #define dump(x) cout << #x << " = " << (x) << endl; #define REP(i, n) for (ll i = 0; i < (n); i++) #define ITOC(n) (char)'0' + n #define KETAUNE(keta, num) setw(keta) << setfill('0') << num #define FOREACH(x, a) for (auto &x : (a)) #define OUT(n) cout << n << endl #define SISHAGONYU(X, base) round(X / (double)base) * base #define KIRISUTE(X, base) X / base *base typedef long long ll; // #include <atcoder/all> // using namespace atcoder; int main() { ll N;cin>>N; vector<ll> A(N); REP(i,N)cin>>A[i]; ll Q;cin>>Q; sort(A.begin(), A.end()); REP(i, Q) { ll x;cin>>x; auto itr = lower_bound(A.begin(), A.end(), x); ll ans = distance(A.begin(), itr); OUT(ans); } }
a11とほぼ同じようなコードになった。違いは - 配列が事前にソートされてるか否か - 「目的の要素は何番目の要素か」と「目的の要素より小さい要素はいくつあるか」
の違い。配列についてはsort関数を適用すれば良いし、指示の違いについては+1をするかどうか。あと少し注意が必要だと思ったのは、配列内に同じ数がある場合。しかし、lower_boundは「指定された要素以上の値が現れる最初の位置のイテレータを取得する」ので、この点については特に考慮する必要はない。同じ数が含まれる場合、その中でも一番左に位置する要素のイテレータを取ってきてくれるので、そこの添字=その数より小さい要素の個数で一致する。
感想
二分探索は添字とか細かい条件をバグらせるのが怖い。たぶん慣れなんだろうけど。あとlower_boundの他にupper_boundもあるらしいが、それはまた別の機会に。
参考: