Garland POJ1759

投稿日：2022/09/13 更新日:2022/09/13

問題

$N$ 個のランプをワイヤーにぶら下げます。一番左のランプ $H_1$ の高さは $A$ 、一番右のランプ $H_N$ の高さは $B$ です。ランプの重みにより、ワイヤーはたるみます。この時以下の3つの式が成立します。

\begin{aligned} &H_1 = A \\ &H_i = \frac{H_{i-1} + H_{i+1}}{2} - 1 (1 < i < N) \\ &H_N = B \\ &H_i \geqq 0 (1 \leqq i \leqq N) \end{aligned}

$N$ と $A$ が与えられるので、これら全ての条件を満たす最小の $B$ を小数第２位まで求めてください。

解法

与えられた式を変形します。

\begin{aligned} H_i = \frac{H_{i-1} + H_{i+1}}{2} - 1 \\ 2H_i = H_{i-1} + H_{i+1} - 2\\ H_{i+1} = 2H_i - H_{i-1} + 2 \end{aligned}

$H_1$ と $H_2$ が定まれば、上の漸化式を用いて全ての $H$ を確定することができます。 $H_1$ は $A$ と与えられているので、適切な $H_2$ を探索すれば良いです。探索には二分探索を用います。 $H_1$ 、 $H_2$ を決めたあと、全ての $H_i$ が0以上でるかを判定します。

実装

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    double a;
    cin >> n >> a;

    double ok = 1e9, ng = -1;
    for(int ii = 0;ii < 100; ++ii){
        double mid = (ok+ng)/2;

        vector<double> h(n);
        h[0] = a;
        h[1] = mid;
        for(int i = 2;i < n; ++i){
            h[i] = 2*h[i-1] - h[i-2] + 2;
        }

        bool valid = true;
        for(int i = 0;i < n; ++i){
            if(h[i] < 0)valid = false;
        }

        if(valid){
            ok = mid;
        }else{
            ng = mid;
        }
    }

    vector<double> h(n);
    h[0] = a;
    h[1] = ok;
    for(int i = 2;i < n; ++i){
        h[i] = 2*h[i-1] - h[i-2] + 2;
    }

    printf("%.2f\n", h[n-1]);
    return 0;
}