基本問題
タイトルからしてアプローチがもろネタバレなのだが、今回は答えで二分探索をするらしい。
この問題の場合、答えの制約として 1 <= K <= 109 があるので、この範囲を探索すればいい。線形探索だとO(NK)となり間に合わないが、二分探索なら N log K になり間に合う。
実装
#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 FOREACH(x, a) for (auto &x : (a)) #define OUT(n) cout << n << endl typedef long long ll; // #include <atcoder/all> // using namespace atcoder; int main() { ll N,K;cin>>N>>K; vector<ll> A(N); REP(i, N) cin>>A[i]; ll L=0, R=1000000000; while(L<R) { ll m = (L+R) / 2; ll num = 0; REP(i, N) { num += m/A[i]; } if (num < K) { L = m+1; } if (num >= K) { R = m; } } OUT(L); }
前回の問題と違う点を考えてみる。
- whileの終了条件の違い
- 判定条件の違い
- Rの値の更新の違い
まず、whileの終了条件が違う。前回は L <= R だったが、今回は L < R だ。この2つは「L==Rになってからも判定を行うか」に違いがある。前回の問題では、配列から特定の値を見つける必要があった。そのため、L==Rとなり探索が完了しても、その値が特定の値かどうかを判定する必要があった。しかし、今回の場合はL==Rになればそれがそのまま答えになるため終了して良い。
次に、判定条件の違いについてだ。前回は m == X, m > X, m < X の3つの判定条件があったが、今回は num < K, num >= K の2つしかない。後者では値が等しかった場合の条件が、期待値の方が小さかった場合の条件とまとめられている。一見、後者でも前者のようにnum == Kのときはmを答えとして返せばいいように見えるが、これは成立しない。例えば m = 5の時に num == Kが成り立つとする。しかし、m=4の時にnum==Kが成り立っているとも限らない。条件を満たしている中で、最小のmを見つける必要があるからだ。
同じ理由で、Rの値の更新の違い(前者はR=m-1, 後者はR=m)も説明できる。前者では目的の値より大きかったらその値は無視して良いのでm-1でできるだけ範囲を狭めたい。しかし、後者ではR=m-1としてしまうと、R=mという条件を満たしている値を探索の範囲から外してしまうことになる。
「条件を満たすxを見つける」、「条件を満たす最小のxを見つける」場合とで意識を変えなければならない気がしている。
応用問題
続いて応用問題。
整数ではなく実数値の二分探索ということで、区間から値を1ずつ狭めていく今までのようなアプローチは取れない。ただし、「絶対誤差または相対誤差が 0.001 未満であれば許容」とあるのでここが鍵か。
実装
#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 FOREACH(x, a) for (auto &x : (a)) #define OUT(n) cout << n << endl typedef long long ll; // #include <atcoder/all> // using namespace atcoder; double calc(double x) { return x*x*x+x; } int main() { ll N;cin>>N; double L=0, R=100; while(R-L>1e-4) { double m = (L+R)/2; double ans = calc(m); if (ans >= N) { R = m; } else { L=m; } } OUT(L); }
ここでも終了条件と、L,Rの更新方法について見ていく。
- 終了条件.
終了条件は「R-L>1e-4」とした。先述のように実数値の二分探索であるため、L<RでLとRが一致するのを待っていたら膨大な時間がかかる。ここでは、LとRの差が10^-4であれば終了とした。問題の条件より、相対誤差は 10^-3まで許容される。x3+xをfとすると、f(L)とf(R)の差が10^-3未満であれば良いことになるので、10^-4であれば十分。
とはいえ、色々調べてたらループ回数を100回とかで決め打ちする方法があるらしい。それについてはまた別の記事で取り上げてみたい。
- 判定条件.
今までの問題とは違い、Lの更新でもRの更新でもm+1などせずにmの値をそのまま代入している。今までの実数値の問題では、L=m+1, R=mで値を更新していた。こうすると、最終的にはLとRの値が「条件を満たす最小値」で一致する。しかし、今回の問題ではLとRは一致しない。L=m, R=mで値を更新すると、LとRは別の値になり、それぞれ「条件を満たさない要素の最大値」、「条件を満たす要素の最小値」の値になる。あとは問題の要件に応じてどちらの値を選択するかを選ぶことになるが、今回の場合は誤差0.001未満であれば許容なのでどちらの値でも良い。
感想
問題ごとにL,Rの値をどのように更新するかを変えたり、実数値の二分探索では誤差を考えなければいけないのはかなり面倒だし認知負荷が高い気がした。今回の問題を特に当たって色々と記事を渉猟してみたのだが、前者は「めぐる式二分探索」という二分探索の共通パターン、後者ではループ回数の固定などの解決策があるらしい。次はこれらのパターンについても取り上げてみたい。