POJ 1759: Garland

概要

N個の提灯が下がった糸を垂らす．片方の端点はAとし，他方をBとする．
このとき，糸は重力にしたがって垂れ下がる．
i番目の提灯の高さをH_iとすると，
H_1 = A, H_N = B,
H_i = (H_(i-1) + H_(i+1)) - 1
が成り立つ．
あるAが与えられたとき，全ての提灯の高さを0以上にするにはBを最小でいくつにすればよいか．

解法

Bの位置について二分探索．．．が差分方程式を解かないといけない．

とすると，与式をいじいじして，

を得る．したがって，

H_1 = A，H_N = Bより，が求められる．

他の人のを見ると，H_2について二分探索している．確かにこちらの方が簡単だ．

int N;
double A;
int main(){
    scanf("%d%lf\n", &N, &A);
    double lb = 0, ub = 1000000;
    for(int k = 0; k < 100; ++k){
        double mid = (lb + ub) / 2;
        double d1 = (mid - A) / (N - 1) - (N - 1);
        bool f = true;
        for(int i = 1; i < N; ++i){
            double p = A + (i-1)*d1 + (i-1)*(i-1);
            f = f && p >= 0;
        }
        if(f){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%.2f\n", ub);
    return 0;
}