読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #364 div2D. As Fast As Possible

二分探索の良い練習問題っぽい。

問題

$n$ 人の生徒と1台のバスが、時刻0において位置0にいる。生徒たちは位置 $L$ にある目的地にたどり着きたい。生徒たちは速度 $v_1$, バスは速度 $v_2$ で移動する。バスは1度に $k$ 人まで同時に乗ることができるが、同じ生徒は1度までしかバスに乗ることができない。全員が目的地に着くまでにかかる時間の最小値は?

制約

$1 \leq n \leq 10000$

$1 \leq L \leq 10^9$

$1 \leq v_1 < v_2 \leq 10^9$

$1 \leq k \leq n$

解法

制約からして二分探索っぽいです。そこで、全員が目的地に着くまでにかかる時間 $T$ の最小値を二分探索で求めることを考えましょう。

時間 $T$ で全員が目的地に着くことが可能かどうかを調べるにはどうすればよいでしょうか?これは、バスが時間 $T$ の間に実際に往復可能であるかを見ればよいです。まず、生徒たちは $m = \lceil n / k \rceil$ 個のグループに分けることができます。貪欲にバスに詰め込んでいくという意味です。また、この  m 個のグループがバスに乗って移動する長さ $l_2$ はグループ間で同じと仮定してよいはずです。あるグループ $g_i$ が 他のグループ $g_j$ よりも長くバスに乗ると、そのぶん $g_j$ がバスに乗れる長さが短くなり、全体としてはより時間がかかってしまうからです。以上より、$l_2$ が満たすべき制約は $(L - l_2) / v_1 + l_2 / v_2 \leq T \cdots (1)$ です(徒歩にかかる時間とバスでの移動にかかる時間の和が $T$ 以下)。今、時間 $T$ での移動が可能かどうかだけがわかればよいので、$l_2$ は式(1)を満たす最小の値として構いません。これは二分探索で求められます(つまり、$T$ についての二分探索の中で $l_2$ についての二分探索をします)。

$l_2$ が決まると、時間 $T$ でバスが往復可能かどうかを次のように判定することができます。これまでの記号に加えて $t_2 = l_2 / v_2$ (各グループがバスでの移動に要する時間) と定義すると、次の1, 2の和が $T$ 以下であればよいです。

  1. バスが生徒を乗せて目的地方向に進むのにかかる時間: $m * t_2$

  2. バスが次のグループを乗せるために逆走するのにかかる時間: $(m - 1) * (l_2 - t_2 * v_1) / (v_1 + v_2)$

$m, m - 1$ はそれぞれの移動の回数を表しています。2について補足をすると、これは相対速度の考えを使っています。バスがあるグループを移動させ終わった直後、次に乗せるグループとの距離の差は $l_2 - t_2 * v_1$ です。生徒はこの区間の左端から右に向かって速度 $v_1$ で、バスは区間の右端から左に向かって速度 $v_2$ で移動しています。これは生徒を固定するとバスが左向きに速度 $v_1 + v_2$ で走っているとみなすことができます。よって2の式が上のようになります。

以下のコードはtorusさんのコードを参考にしました。ちなみに $l_2$ の最小値はコメントアウトした箇所のように数式を解いて求めることもできます( $T$ も同様にできるらしいですがよくわからず……)。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto&& x : v){cerr << x << " ";} cerr << endl
#define printVV(vv) for(auto&& v : vv){for(auto&& x : v){cerr << x << " ";}cerr << endl;}
#define printP(p) cerr << p.first << " " << p.second << endl
#define printVP(vp) for(auto&& p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;
typedef vector<vector<int>> Graph;

double n, L, v1, v2, k;

double busLenMin(double T) {
    double lb = 0, ub = L;
    rep(_, 100) {
        double l2 = (lb + ub) / 2;
        ((L - l2) / v1 + l2 / v2 <= T ? ub : lb) = l2;
    }
    return lb;
}

// double busLenMin(double T) {
//     return v2 * (L - v1 * T) / (v2 - v1);
// }

bool check(double T) {
    double l2 = busLenMin(T);
    double t2 = l2 / v2;
    double m = ceil(n / k);
    return m * t2 + (m - 1) * (l2 - t2 * v1) / (v1 + v2) <= T;
}

signed main() {
    cin >> n >> L >> v1 >> v2 >> k;
    double lb = 0, ub = 1e10;
    rep(_, 100) {
        double mid = (lb + ub) / 2;
        (check(mid) ? ub : lb) = mid;
    }
    printf("%.10f\n", lb);
}