Official

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)\) が凸関数であることは、「凸関数の和は凸関数である」という定理を用いるか、微分を用いることで示せます。

入力例1における f(n)

以下、この問題の2つの解法を示します。

解法1 三分探索

凸関数の最小値を求める問題は、三分探索というアルゴリズムを使うことで解くことができます。これは、「\(f(n)\) が最小値をとる \(n\)\(l\leq n\leq r\) の範囲に存在する」(*) ことが保証される \(l,r\) を設定し、条件 (*) を満たしながら \(l\)\(r\) を少しずつ近づけていくことで、答えの \(n\) を見つけるアルゴリズムです。具体的なアルゴリズムは以下の通りです。

  1. 条件 (*) を満たすように \(l,r\) の初期値を設定する。
  2. \(m_1 := (2l+r)/3, m_2 := (l+2r)/3\) とする。\(f(m_1) < f(m_2)\) ならば \(r \leftarrow m_2\) とし、 そうでないならば \(l \leftarrow m_1\) とする。
  3. 答えが含まれることが保証される範囲 \([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: