😽

ABC257 D-Jumping Takahashi 2(C++)

2023/01/01に公開約5,500字

問題概要

問題文

二次元平面にN個の点がある。点iは、位置(x_i,y_i)にあり、には値P_iが定められている。
あなたは、最初整数Sを決める。
このSに対して、次の条件を満たすときに限り点iから点jに移動できる。

  • P_iS\geq |x_i-x_j|+|y_i-y_j|

次の条件を満たすようなSの最小値を求めてください。

  • スタート地点を適切に定めることで、どの点にも移動を繰り返して到達できる。

制約

  • 1\leq N\leq 200
  • |x_i|,|y_i|\leq10^9
  • 1\leq P_i \leq 10^9
  • i\neq j\Rightarrow (x_i,y_i)\neq(x_j,y_j)
  • 入力はすべて整数

メモ

言い換え

なんかややこしいので、グラフの言葉に書き換えてしまいましょう。
N個の点を、有向グラフの頂点とみれば次のように言えます

  • P_iS\geq |x_i-x_j|+|y_i-y_j|を満たすその時に限り、頂点iから頂点jへの有向辺が存在する

このグラフを、G(S)と書くことにします。

条件のほうは、次のように言い換えられます

  • 頂点sが存在して、任意の頂点tに対してsからtへのパスが存在する。

要は、G(S)が条件を満たすような最小のSを求めればよいのです。

解法

条件は、BFSなりDFSなりで判定できます。少し遅くはなりますが、O(N^3)でワーシャルフロイド法を用いても間に合います。
Sの方は、二分探索を使えば高速に求まるのでOK!!!

二分探索で求まる理由

Sに単調性があることに注目する!

  • あるXが存在してG(X)が条件を満たすとする。この時、任意のY\geq Xに対してG(Y)は条件を満たす。

これは、

  • P_iX\geq |x_i-x_j|+|y_i-y_j|\Rightarrow P_iY\geq |x_i-x_j|+|y_i-y_j|(\because P_iY\geq P_iX)

より、G(X)におけるs-tパスがG(Y)においても存在することからわかります。


したがって、ある境界kが存在してS\geq kなる任意のSに対してG(S)は条件を満たします。逆に、S<kなる任意のSに対してG(S)は条件を満たしません。
このkこそが答えです。

計算量は、O(N^2\log{S_{\max}})O(N^3\log{S_{\max}})ぐらい。S_{\max}は答えとしてありうる最大値です。

実装上の注意

さて、オーバーフローに気を付ける必要があります。特に、この問題ではかなりシビアです。
二分探索では探索範囲の上限(=S_{\max})を決めますが、下手にS_{\max}=10^{18}とかにするとP_iSという値がめちゃくちゃ大きくなり、判定がバグります。ちゃんと見積もれば、S_{\max}=4\times10^9で十分なことが分かります。


筆者はここで悩みまくりました...
https://twitter.com/ac2000_cp/status/1609410291229667330

実装例

main.cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i, N)  for(int i=0;i<(N);i++)
using ll = long long;
using graph = vector<vector<int>>;
const int INF = 1e9;
ll solve(int n,const vector<ll>&x,const vector<ll>&y,const vector<ll>&p){
    auto check=[&](ll S)-> bool {
        graph g(n);
        rep(i,n)rep(j,n){
            ll dx=abs(x[i]-x[j]);
            ll dy=abs(y[i]-y[j]);
            if(S*p[i]>=dx+dy)g[i].push_back(j);     //有向辺を張る
        }

        rep(s,n){
            vector<bool> vis(n,false);
            //DFS
            auto dfs=[&](const auto&f,int v)-> void {
                vis[v]=true;
                for(auto nex:g[v]){
                    if(vis[nex])continue;
                    f(f,nex);
                }
            };
            dfs(dfs,s);
            bool flag=true;
            rep(v,n){
                if(!vis[v])flag=false;
            }
            if(flag)return true;
        }
        return false;
    };

    ll ok=4ll*INF;
    ll ng=0;
    while(abs(ng-ok)>1){
        ll mid=(ok+ng)/2;
        if(check(mid))ok=mid;
        else ng=mid;
    }
    return ok;
}
int main() {
    ll n;
    cin>>n;
    vector<ll> x(n),y(n),p(n);
    rep(i,n){
        cin>>x[i]>>y[i]>>p[i];
    }
    cout<<solve(n,x,y,p)<<endl;
}
main.cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i, N)  for(int i=0;i<(N);i++)
using ll = long long;
using graph = vector<vector<int>>;
const int INF = 1e9;
ll solve(int n,const vector<ll>&x,const vector<ll>&y,const vector<ll>&p){
    auto check=[&](ll S)-> bool {
        graph g(n);
        rep(i,n)rep(j,n){
            ll dx=abs(x[i]-x[j]);
            ll dy=abs(y[i]-y[j]);
            if(S*p[i]>=dx+dy)g[i].push_back(j);     //有向辺を張る
        }

        rep(s,n){
	    //BFS
            vector<bool> vis(n,false);
            queue<int> que;
            que.push(s);
            while(!que.empty()){
                int v=que.front();
                que.pop();
                vis[v]=true;
                for(auto nex:g[v]){
                    if(vis[nex])continue;
                    que.push(nex);
                }
            }
            bool flag=true;
            rep(v,n){
                if(!vis[v])flag=false;
            }
            if(flag)return true;
        }
        return false;
    };

    ll ok=4ll*INF;
    ll ng=0;
    while(abs(ng-ok)>1){
        ll mid=(ok+ng)/2;
        if(check(mid))ok=mid;
        else ng=mid;
    }
    return ok;
}
int main() {
    ll n;
    cin>>n;
    vector<ll> x(n),y(n),p(n);
    rep(i,n){
        cin>>x[i]>>y[i]>>p[i];
    }
    cout<<solve(n,x,y,p)<<endl;
}
  • ワーシャルフロイド法を使う方法(提出)
main.cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i, N)  for(int i=0;i<(N);i++)
using ll = long long;
const int INF = 1e9;
ll solve(int n,const vector<ll>&x,const vector<ll>&y,const vector<ll>&p) {
    //条件を満たすかどうか
    auto check=[&](ll S)-> bool {
        vector<vector<bool>> g(n,vector<bool>(n,false));    //g[i][j]=i->jに動けるか?
        rep(i,n)rep(j,n){
            if(i==j){
                g[i][j]=true;
            }
            ll dx=abs(x[i]-x[j]);
            ll dy=abs(y[i]-y[j]);
            if(S*p[i]>=dx+dy)g[i][j]=true;
        }
        //ワーシャルフロイド
        rep(k,n)rep(i,n)rep(j,n){
            if(g[i][k]&&g[k][j])g[i][j]=true;
        }
        rep(s,n){
            bool fl=true;
            rep(v,n){
                if(!g[s][v]){
                    fl=false;
                }
            }
            if(fl)return true;
        }   
        return false;
    };
    //二分探索
    ll ok=4ll*INF;
    ll ng=0;
    while(abs(ng-ok)>1){
        ll mid=ok+(ng-ok)/2;
        if(check(mid))ok=mid;
        else ng=mid;
    }
    return ok;
}
int main(){
    //入力
    int n;
    cin>>n;
    vector<ll> x(n),y(n),p(n);
    rep(i,n){
        cin>>x[i]>>y[i]>>p[i];
    }
    cout<<solve(n,x,y,p)<<endl;
}

Discussion

ログインするとコメントできます