問題

D – Jumping Takahashi 2

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/6/25 リアルタイム参加　解法わからず。

解法

• あとで書く。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
// using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

int N;
vector<ll> x;
vector<ll> y;
vector<ll> P;

bool f(ll mid) {
  vector<vector<int>> canVisit(N, vector<int>(N, 0));
  rep(i, N) {
    rep(j, N) {
      ll dist = abs(x[i] - x[j]) + abs(y[i] - y[j]);
      if (dist <= P[i] * mid) {
        canVisit[i][j] = 1;
      }
    }
  }

  rep(k, N) {
    rep(i, N) {
      rep(j, N) {
        // if (canVisit[k][j] && canVisit[i][k]) {
        //   canVisit[i][j] = true;
        // }
        canVisit[i][j] |= canVisit[k][j] & canVisit[i][k];
      }
    }
  }

  rep(i, N) {
    bool flg = true;
    rep(j, N){
      if(canVisit[i][j] == 0) {
        flg = false;
      }
    }
    if(flg) {
      return true;
    }
  }

  return false;
}

int main() {
  cin >> N;
  
  x.resize(N);
  y.resize(N);
  P.resize(N);
  rep(i, N) {
    cin >> x[i] >> y[i] >> P[i];
  }

  ll wa = 0;
  ll ac = 4000000000LL;
  while(1 < ac - wa) {
    ll mid = (ac + wa) / 2;
    if (f(mid)) {
      ac = mid;
    } else {
      wa = mid;
    }
  }

  cout << ac << endl;
  return 0;
}