D - Freefall Editorial by yuto1115
解説操作を行う回数を \(n\ (n \geq 0)\) とおくと、高橋くんが地面に到達する時刻は \(f(n) = Bn+\frac{A}{\sqrt{n+1}}\) という式で表されます。よってこの問題は、\(n\) が \(0\) 以上の整数値を取る時の \(f(n)\) の最小値を求める問題になります。
以下、\(f\) を \(0\) 以上の実数に対して定義された関数として扱います。
まず、答えの範囲を見積もってみましょう。\(n >= A/B\) のとき、\(f(n) > Bn \geq A = f(0)\) より \(f(n) > f(0)\) であるため、\(0 \leq n < A/B\) の範囲だけ考えれば良いことがわかります。しかし、この問題における \(A,B\) は大きいため、候補となるすべての \(n\) について \(f(n)\) を計算することはできません。
この問題を解くためには、\(f\) が凸関数であることに気づく必要があります。下の画像は入力例1における \(y=f(x)\) のグラフ (横軸が \(x\)) です。このように下にふくらんだ関数のことを凸関数といいます (正確な定義は https://ja.wikipedia.org/wiki/凸関数 をご参照ください)。\(f(x)\) が凸関数であることは、「凸関数の和は凸関数である」という定理を用いるか、微分を用いることで示せます。
以下、この問題の2つの解法を示します。
解法1 三分探索
凸関数の最小値を求める問題は、三分探索というアルゴリズムを使うことで解くことができます。これは、「\(f(n)\) が最小値をとる \(n\) は \(l\leq n\leq r\) の範囲に存在する」(*) ことが保証される \(l,r\) を設定し、条件 (*) を満たしながら \(l\) と \(r\) を少しずつ近づけていくことで、答えの \(n\) を見つけるアルゴリズムです。具体的なアルゴリズムは以下の通りです。
- 条件 (*) を満たすように \(l,r\) の初期値を設定する。
- \(m_1 := (2l+r)/3, m_2 := (l+2r)/3\) とする。\(f(m_1) < f(m_2)\) ならば \(r \leftarrow m_2\) とし、 そうでないならば \(l \leftarrow m_1\) とする。
- 答えが含まれることが保証される範囲 \([l,r]\) が十分に小さいならば、終了する。さらに範囲を小さくしたい場合は 2. を繰り返す。
今回は \(n\) が整数の範囲での最小値を求めたいため、\(l,r,m_1,m_2\) 等の変数は整数にします (実数にすれば、実数の範囲での最小値を求めることもできます)。
三分探索では、操作2を行うごとに答えの含まれる範囲 \([l,r]\) が約 \(\frac{2}{3}\) になるため、\(f(n)\) が最小値をとる \(n\) を非常に高速に求めることができます。実際、本問題においては \(l=0,r=A/B\) として初期値を設定することで、操作2を最大 100 回ほど行えば答えを求めることができ、十分に高速です。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll a, b;
cin >> a >> b;
auto f = [&](ll n) -> double {
return (double) a / sqrt(n + 1) + (double) b * n;
};
ll l = 0, r = a / b;
while (r - l > 2) {
ll m1 = (l * 2 + r) / 3;
ll m2 = (l + r * 2) / 3;
if (f(m1) > f(m2)) l = m1;
else r = m2;
}
double ans = a;
for (ll i = l; i <= r; i++) {
ans = min(ans, f(i));
}
cout << fixed << setprecision(10) << ans << endl;
}
解法2 微分
以下、高校数学の微分の知識を前提とします。
\(f'(x) = B-\frac{A}{2(x+1)\sqrt{x+1}}\) より \(f'(x)=0 \Leftrightarrow x = (\frac{A}{2B})^{\frac{2}{3}}-1\) であるため、\(f(x)\) は(\(x\) が実数の範囲において)\(x = (\frac{A}{2B})^{\frac{2}{3}}-1\) で最小値を取ります。本問題においては、\(x\) が整数の範囲での最小値を求める必要がありますが、\(f\) の凸性より \(\lfloor (\frac{A}{2B})^{\frac{2}{3}} \rfloor\) と \(\lceil (\frac{A}{2B})^{\frac{2}{3}} \rceil\) のみを調べれば良いことがわかります。なお、数値誤差等の問題もあるため、余裕を持って前後 \(\pm 5\) 程度の範囲を調べるとよいでしょう。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll a, b;
cin >> a >> b;
auto f = [&](ll n) -> double {
return (double) a / sqrt(n + 1) + (double) b * n;
};
ll argmin = pow((double) a / (b * 2), 2. / 3.) - 1;
ll l = max(argmin - 5, 0LL), r = min(argmin + 5, a / b);
double ans = a;
for (ll i = l; i <= r; i++) {
ans = min(ans, f(i));
}
cout << fixed << setprecision(10) << ans << endl;
}
posted:
last update: