Jumping Takahashi 2 [日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257） D]

https://atcoder.jp/contests/abc257/tasks/abc257_d

前提知識

• 二分探索
• BFS （BFSを使わなくても良いやり方もある）

解説

https://atcoder.jp/contests/abc257/submissions/32753407

何から考え始めるか

いつものように全探索解法がないか探してみる。
全探索できそうなのはSの値か、始点となるジャンプ台くらいな感じがする。
この辺りから考え始めていき、Sの値の全探索の方で使えそうな属性が浮かび上がってくる。

Sの値を増やしていくとジャンプすることができる遷移がどんどん増えていくことになる。
そして、大事なのが、Sの値を増やしても前使えた遷移が使えなくなることがないということ。
ここから何が言えるかというと、Sの値をどんどん増やしていくと、
あるSの値を境に高橋君の目的が達成されるようになるということである。
問題では、最低何回訓練を行う必要があるかという問であるので、ちょうどこの「あるSの値」が答えになっている。

ここまで考察が進んでいれば、あとは知っていれば解法のとっかかりが見えてくる。
このようなある境界より前は条件を満たさず、ある境界より後は条件を満たすような境界を探すときは、
二分探索が有効である。
もし知らない場合は、この方針で解くのは難しいだろう。

二分探索

以下のような評価のための関数を用意しよう。

check(S) := 指定されたSについて高橋君の目的を達成することができるか

二分探索で問題になるのが探索範囲であるが、xyの値の範囲を見ると右辺の最大値は4×10⁹になりそうである。
Pの最小値が1であることを考えると探索範囲の最大値は4×10⁹以上にしておく必要がありそうだ。
自分は念のため+1した値を最大値とした。

計算過程でintにおさまらない可能性があるので、intは使わずlong longで変数を各種用意している。

check関数の中身

あとは、check関数が適切に実装できれば答えになる。
色々解法があるように思えるが、始点とするジャンプ台を全探索することで解いた。
各全探索では、始点とするジャンプ台startからの遷移で他のジャンプ台に行けるかどうかの判定が必要となる。
これはbfsを使って判定している。
bfsをする過程で到達済みの要素を保存しておくことになるが、これがbfs後に到達可能性な要素となる。
bfsを到達可能性判定に使用することもよくあるので覚えておくといい。
1つでも全部到達可能な始点があればtrueで、1つもないならfalseと返せばcheck関数完成。

int N;
ll x[201], y[201], P[201];

bool canMove(ll S, int from, int to) {
    return P[from] * S >= abs(x[from] - x[to]) + abs(y[from] - y[to]);
}

bool check(ll S) {
    rep(start, 0, N) {
        set<int> visited;
        queue<int> que;

        visited.insert(start);
        que.push(start);

        while (!que.empty()) {
            int cur = que.front();
            que.pop();

            rep(to, 0, N) if (to != cur) {
                if (canMove(S, cur, to) && !visited.count(to)) {
                    visited.insert(to);
                    que.push(to);
                }
            }
        }

        if (visited.size() == N) return true;
    }

    return false;
}

void _main() {
    cin >> N;
    rep(i, 0, N) cin >> x[i] >> y[i] >> P[i];

    ll ng = -1, ok = 4000000001LL;
    while (ng + 1 != ok) {
        ll md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}