CFR 701 D. As Fast As Possible ( Math + Binary Search )

Problem - D - Codeforces
本番中 "reversal of the bus, take place immediately and this time can be neglected" を「バスの移動は時間がかからない」と勘違いし、とけなかった。。反転だけの時間という事。

Let's think about binary searching minimum time. It is instinctive that each group of students will be on the bus for the same amount of time.
We have 2 things we want to make sure, with a time limit of T:
1. Considering each pupil, ( L - bus_travel_dis ) / V1 + bus_travel_dis / V2 ≤ T.
2. Considering the bus, the total time it spends going back and forth should not exceed T.
=> number_of_groups * bus_travel_dis / V2 + ( number_of_groups - 1 ) * ( bus_travel_dis - bus_travel_time * V1 ) / ( V1 + V2 ) ≤ T.

int N, L, V1, V2, K;

bool ok( double x ){
    double lb = 0, rb = L; // min bus length that students will not be late
    for( int i = 0; i < 100; ++i ){
        double mid = ( lb + rb ) / 2;
        if( ( 1.0 * L - mid ) / V1 + mid / V2 <= x ) rb = mid;
        else lb = mid;
    }

    int g = ( N + K - 1 ) / K; // how many groups of students for bus
    return lb * g / V2 + ( lb - lb / V2 * V1 ) * ( g - 1 ) / ( V1 + V2 ) <= x; // if the bus will make on time
}

void solve(){
    cin >> N >> L >> V1 >> V2 >> K;

    double lb = 0, rb = 1e10;
    for( int i = 0; i < 100; ++i ){
        double mid = ( lb + rb ) / 2;
        if( ok( mid ) ) rb = mid;
        else lb = mid;
    }

    cout << fixed << setprecision( 8 ) << lb << "\n";
}