二分探索を使った問題で計算量を削減したい

Question

問題

AtCoder Beginner Contest 257 D問題

方針

Nの値が200以下と比較的小さいので、それぞれの点を始点として、全ての点に到達可能かを全探索によって判定します。ここで、Sの値については二分探索を用います。Sの値をmidで決め打ちする度に重みなしグラフを作り、上の判定を行うと言った要領です。

コード

（必要に応じて揃えた関数が長いですが、メインは下のsolve()関数の部分です）

#include <bits/stdc++.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long

/* absolute value of x */
ll absolute(ll x) {
    if (x < 0) {
        return -x;
    }
    else {
        return x;
    }
}

/* search distance from start node using BFS */
vector<ll> bfs(vector<vector<ll>> graph, ll start) {
    ll inf = 9223372036854775807;
    deque<ll> data = {start};
    vector<ll> dist = {};
    for (ll i = 0; i < graph.size(); i++) {
        dist.push_back(inf);
    }
    dist.at(start) = 0;
    while (data.size() > 0) {
        ll pos = data.at(0);
        data.pop_front();
        for (ll el: graph.at(pos)) {
            if (dist.at(el) == inf) {
                dist.at(el) = dist.at(pos) + 1;
                data.push_back(el);
            }
        }
    }
    return dist;
}

/* minimum */
ll min(vector<ll> li) {
    ll x = li.at(0);
    for (ll el: li) {
        if (el < x) {
            x = el;
        }
    }
    return x;
}

/* infinity */
ll inf = 9223372036854775807;

void solve() {
    ll N; cin >> N;
    vector<vector<ll>> loc = {};
    vector<ll> jump = {};
    for (ll i = 0; i < N; i++) {
        loc.push_back({});
        jump.push_back(inf);
    }

    for (ll i = 0; i < N; i++) {
        ll x, y, P; cin >> x >> y >> P;
        loc.at(i) = {x, y};
        jump.at(i) = P;
    }

    vector<vector<vector<ll>>> graph = {};
    for (ll i = 0; i < N; i++) {
        graph.push_back({});
    }
    for (ll i = 0; i < N - 1; i++) {
        for (ll j = i + 1; j < N; j++) {
            ll d = absolute(loc.at(i).at(0) - loc.at(j).at(0)) + absolute(loc.at(i).at(1) - loc.at(j).at(1));
            graph.at(i).push_back({j, d});
            graph.at(j).push_back({i, d});
        }
    }

    vector<ll> ans = {};
    for (ll i = 0; i < N; i++) {
        ll left = -1;
        ll right = 4000000001;
        while (left + 1 < right) {
            ll mid = (left + right) / 2;
            vector<vector<ll>> mini_graph = {};
            for (ll j = 0; j < N; j++) {
                mini_graph.push_back({});
            }
            for (ll j = 0; j < N; j++) {
                for (vector<ll> el: graph.at(j)) {
                    ll nx = el.at(0);
                    ll d = el.at(1);
                    if (jump.at(j) * mid >= d) {
                        mini_graph.at(j).push_back(nx);
                    }
                }
            }

            vector<ll> dist = bfs(mini_graph, i);
            ll cnt = 0;
            for (ll d: dist) {
                if (d != inf) {
                    cnt++;
                }
            }

            if (cnt == N) {
                right = mid;
            }
            else {
                left = mid;
            }
        }
        ans.push_back(right);
    }
    cout << min(ans) << endl;

}

int main() {
    solve();
}

試したこと

上記コードでは幅優先探索を用いましたが、これの他に深さ優先探索（再帰を用いたもの、スタックキューを用いたもの）も試しました。しかしこれはかえって計算時間が長くなりました。二分探索の
左端右端の値も適当に取るのではなくあり得る範囲の最小の分しか取っていません。しかしいずれもうまくいかず、手元の環境だと例えば

200
999999684 -999999130 1
-999999641 -999999665 1
-999999300 999999389 1
999999303 999999477 1
-999999577 -999999307 1
999999578 999999227 1
-999999653 -999999086 1
-999999214 999999268 1
-999999300 999999708 1
999999721 999999494 1
-999999172 -999999956 1
-999999623 -999999568 1
-999999538 999999130 1
999999324 999999228 1
-999999961 999999880 1
-999999876 999999662 1
999999492 999999840 1
999999070 -999999509 1
999999843 999999784 1
-999999566 999999916 1
999999627 -999999255 1
999999464 999999782 1
999999333 999999879 1
999999766 999999775 1
-999999189 -999999037 1
-999999604 -999999999 1
-999999136 999999718 1
-999999280 -999999111 1
-999999211 -999999073 1
-999999837 999999621 1
999999656 -999999650 1
999999356 999999237 1
-999999538 -999999647 1
-999999096 -999999385 1
-999999392 999999778 1
-999999786 999999610 1
-999999888 -999999630 1
999999754 -999999035 1
-999999863 -999999755 1
-999999905 -999999958 1
999999538 -999999530 1
-999999948 999999427 1
999999243 -999999388 1
-999999322 -999999901 1
-999999804 -999999635 1
-999999701 999999400 1
999999064 999999495 1
-999999526 999999294 1
999999923 -999999166 1
-999999934 999999410 1
999999836 999999756 1
-999999414 -999999562 1
999999847 999999274 1
999999645 999999262 1
999999909 999999899 1
999999276 -999999693 1
-999999756 999999670 1
-999999334 -999999132 1
999999016 -999999961 1
999999313 -999999448 1
999999140 999999473 1
999999444 -999999285 1
-999999494 999999984 1
999999700 999999847 1
999999829 -999999076 1
999999322 999999141 1
999999492 999999747 1
-999999265 999999096 1
-999999477 999999168 1
-999999005 -999999602 1
-999999697 -999999114 1
-999999630 -999999777 1
999999402 -999999777 1
-999999028 999999733 1
999999279 999999839 1
999999036 999999028 1
-999999257 -999999079 1
-999999159 -999999857 1
-999999433 999999651 1
999999649 999999253 1
-999999027 999999737 1
999999560 999999833 1
-999999064 999999741 1
-999999077 999999527 1
-999999767 -999999204 1
-999999769 999999002 1
-999999934 -999999929 1
999999244 999999730 1
-999999521 999999484 1
-999999292 -999999773 1
-999999680 999999889 1
-999999611 999999237 1
-999999422 -999999538 1
-999999901 999999039 1
-999999869 -999999243 1
-999999263 999999181 1
999999523 -999999550 1
999999757 -999999579 1
-999999533 -999999401 1
999999971 -999999914 1
-999999033 999999065 1
999999185 999999375 1
999999899 999999984 1
-999999184 999999094 1
-999999203 -999999711 1
999999649 999999987 1
-999999929 999999924 1
999999483 999999096 1
999999200 -999999799 1
999999370 -999999380 1
999999937 999999593 1
-999999817 999999597 1
999999951 999999376 1
-999999795 -999999674 1
-999999538 -999999822 1
999999888 -999999348 1
-999999469 999999897 1
-999999174 999999007 1
-999999803 -999999584 1
-999999238 999999574 1
-999999234 999999939 1
-999999051 -999999089 1
999999127 -999999225 1
999999166 -999999325 1
999999648 -999999393 1
999999063 -999999588 1
999999097 999999772 1
-999999345 -999999847 1
-999999157 -999999812 1
-999999849 999999693 1
999999994 -999999377 1
999999845 999999791 1
-999999848 -999999544 1
-999999802 999999116 1
999999395 -999999137 1
-999999824 -999999592 1
999999084 -999999747 1
-999999445 -999999191 1
-999999333 -999999207 1
-999999867 -999999720 1
-999999864 -999999725 1
-999999178 999999292 1
-999999787 999999040 1
999999146 999999050 1
-999999499 -999999634 1
999999937 -999999689 1
999999168 -999999056 1
999999443 -999999183 1
999999174 -999999054 1
999999781 999999539 1
-999999725 999999225 1
-999999834 -999999339 1
-999999877 999999408 1
999999470 999999854 1
999999546 999999302 1
-999999865 999999247 1
999999311 999999164 1
999999911 -999999730 1
999999732 999999112 1
999999352 -999999910 1
-999999543 -999999859 1
-999999225 999999105 1
-999999134 -999999270 1
999999399 -999999499 1
999999728 -999999139 1
999999574 -999999686 1
999999759 999999135 1
-999999251 999999711 1
-999999009 999999952 1
999999615 999999301 1
-999999403 -999999364 1
-999999874 -999999843 1
999999493 999999018 1
999999708 -999999976 1
999999075 -999999909 1
999999454 999999941 1
-999999443 -999999377 1
-999999116 -999999895 1
999999039 -999999657 1
999999142 999999424 1
999999569 999999933 1
999999966 -999999254 1
-999999715 999999436 1
999999940 999999367 1
-999999731 -999999247 1
-999999182 999999029 1
999999216 -999999348 1
999999231 -999999870 1
-999999431 999999174 1
999999123 999999307 1
-999999223 -999999352 1
999999857 999999182 1
-999999824 -999999728 1
999999429 999999173 1
999999499 -999999802 1
999999135 999999977 1
-999999331 999999101 1
-999999140 -999999607 1
999999223 999999058 1
999999071 999999388 1

のようなケースに対しては12495msを要しており、制限時間の3000msまでは程遠い状況です。

質問

上記のように試せる部分で余計な計算を省く工夫をしては見ましたがいずれも抜本的な改善には至りません。半ば丸投げのような形になってしまい申し訳ございませんが、どこか見落としているところや改善しうるところはありますでしょうか？お力添え頂けるところがあれば、何卒よろしくお願いします。

Comments

[fana]

> Nの値が200以下と比較的小さいので、それぞれの点を始点として、全ての点に到達可能かを全探索によって判定します。

よくわからんけど，ここから考え直すべきなのでは？
（この手のやつって，「候補全てについてやってみて～」みたいな方法でいけるように制限時間が設けられているものなのか？っていう）

[fana]

仮に始点に関しては全部やってみるのだとしても，何故Sを二分探索せねばならないのか？　というのが疑問．ここにもうちょっとマシなやり方があるのではなかろうか？

[Zuishin]

200 なら「全探索しろ」という出題意図だと思いますよ。

二分探索はどうでしょうね。単純に全ジャンプ台から他のジャンプ台に移るのに必要な S の最小値をフロイド・ワーシャル法の応用で求めたら済みそうな気もしますが。

質問のタイトルには「計算量を削減したい」とありますが、「計算量」はアルゴリズムに依存するので、これを削減するにはアルゴリズムの変更が必要です。
アルゴリズムを変更していいなら、解説を読めばいいのではないですか？

[Zuishin]

解説を見てみました。
まさに私の思いつきと同じアルゴリズムのものがありました。

https://atcoder.jp/contests/abc257/editorial/4174

[fana]

なんだ，「解説」なんてものが存在するのならば質問する理由がわからないな…
…とか思ったら，「公式」とかついてる一番上の解説がいきなり

> 高橋君が訓練を行う回数で二分探索を行います。

って書いてるのね．つまり，
【解説を信じるならば今のやり方で制限時間に間に合うハズ(?)なのに，何故間に合わないのか？】っていう意味合いの質問なのかな？

[kay_ventris4]

お二方ありがとうございます。
＞【解説を信じるならば今のやり方で制限時間に間に合うハズ(?)なのに，何故間に合わないのか？】っていう意味合いの質問なのかな？
解説を見てこの解法を思いついたわけでもないのですが、おおまかな方針が実際のところ一番上にある解答と一致しているのに、可能な限り工夫をしても何故通らないのか、という趣旨の質問です。しっかりと明記しておくべきでした。ご指摘ありがとうございます。

[fana]

コードが何やってるのかはわからんので，アルゴリズム実装の不備（バグみたいな事柄）については言えませんが…

速度を求めている場合には vector::at() とかはまず避けるんじゃないのかな，とか．
vector を値渡ししたり戻り値として返したりとかもしないんじゃないかな，とか．
あと， vector<ll> ans というのも要らないように見える（現時点での最小値を１だけ保持していればよいのでは）とか．

まぁ，こんなのがどの程度有意に実行速度に効くのかはわからないですが．

Answer 1

ループのネストの順番を入れ替えて、重い処理(mini_graphの作成)を実行する回数を少しでも減らしましょう。

#include <bits/stdc++.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long

/* absolute value of x */
ll absolute(ll x) {
    if (x < 0) {
        return -x;
    }
    else {
        return x;
    }
}

/* search distance from start node using BFS */
vector<ll> bfs(vector<vector<ll>> graph, ll start) {
    ll inf = 9223372036854775807;
    deque<ll> data = {start};
    vector<ll> dist = {};
    for (ll i = 0; i < graph.size(); i++) {
        dist.push_back(inf);
    }
    dist.at(start) = 0;
    while (data.size() > 0) {
        ll pos = data.at(0);
        data.pop_front();
        for (ll el: graph.at(pos)) {
            if (dist.at(el) == inf) {
                dist.at(el) = dist.at(pos) + 1;
                data.push_back(el);
            }
        }
    }
    return dist;
}

/* infinity */
ll inf = 9223372036854775807;

void solve() {
    ll N; cin >> N;
    vector<vector<ll>> loc = {};
    vector<ll> jump = {};
    for (ll i = 0; i < N; i++) {
        loc.push_back({});
        jump.push_back(inf);
    }

    for (ll i = 0; i < N; i++) {
        ll x, y, P; cin >> x >> y >> P;
        loc.at(i) = {x, y};
        jump.at(i) = P;
    }

    vector<vector<vector<ll>>> graph = {};
    for (ll i = 0; i < N; i++) {
        graph.push_back({});
    }
    for (ll i = 0; i < N - 1; i++) {
        for (ll j = i + 1; j < N; j++) {
            ll d = absolute(loc.at(i).at(0) - loc.at(j).at(0)) + absolute(loc.at(i).at(1) - loc.at(j).at(1));
            graph.at(i).push_back({j, d});
            graph.at(j).push_back({i, d});
        }
    }

    ll left = -1;
    ll right = 4000000001;
    while (left + 1 < right) {
        ll mid = (left + right) / 2;
        vector<vector<ll>> mini_graph = {};
        for (ll j = 0; j < N; j++) {
            mini_graph.push_back({});
        }
        for (ll j = 0; j < N; j++) {
            for (vector<ll> el: graph.at(j)) {
                ll nx = el.at(0);
                ll d = el.at(1);
                if (jump.at(j) * mid >= d) {
                    mini_graph.at(j).push_back(nx);
                }
            }
        }

        bool flag = false;
        for (ll i = 0; i < N; i++) {
            vector<ll> dist = bfs(mini_graph, i);
            ll cnt = 0;
            for (ll d : dist) {
                if (d != inf) {
                    cnt++;
                }
            }

            if (cnt == N) {
                flag = true;
                break;
            }
        }
        if (flag) {
            right = mid;
        }
        else {
            left = mid;
        }
    }
    cout << right << endl;

}

int main() {
    solve();
}

Comments

[actorbug]

「攻撃的な表現などを含む不快な回答」という指摘を受けたので、最低限の解説に書き換えました

[kay_ventris4]

ご丁寧にありがとうございました。
自分の解答ではbfsをする回数を出来るだけ減らそうとしていましたが、結果としてmini_graphを余計な数生成していたという事ですね。とてもスッキリしました。

[actorbug]

ちなみに、bfsの回数もこちらのほうが少なくなっています。すべてのジャンプ台に移動できるジャンプ台が1つ見つかった時点で探索を打ち切るためです。