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

裏紙

ほぼ競プロ、たまに日記

ARC 025 C - ウサギとカメ

問題

C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder

イデア

方針はすぐに思いついたけど、実装でバグらせまくって時間かかったのでメモ。

まず、各頂点どうしの最短経路を求めておいた方がよさそうだな、と思いワーシャルフロイドだとO(n^3)かかってしまうので間に合わないだろうなあということで、辺の総数mが頂点に対して結構少ないので、優先度付きキューを用いたダイクストラ法を各頂点に対して適用することでO(nm log(n))でこれを実現できる。

そして、条件を満たすような目的地Aとウサギのスタート地点Bとカメのスタート地点Cの組み合わせの個数を求めたいわけだが、組み合わせを総当りするのではO(n^3)かかってしまうので間に合わないと思われる。

そこで、目的地Aを固定して考えてみることにする。ここで、問題について:「カメが最適に動く時にウサギがどんな動きをしてもカメより後に着く」というのは、「ウサギが仮に最適な動きをしてもカメが先に着く」ようにするということであるから、頂点iからAまでの最短距離をd(i)とするとウサギが毎秒Rメートル、カメが毎秒Tメートルで進むことに留意すれば、時間に着目して満たすべき条件は \frac{d(C)}{T} \lt \frac{d(B)}{R}ということになる。double型は扱いたくないので、式変形して d(C)*R \lt d(B)*Tを満たすようなBCの組を数え上げれば良いということになる。

BCの組を数える方法について、Bを固定した時に、Cの候補が何個あるのかということを二分探索により求めることが可能である。Bを固定することによって、さきほどの満たすべき条件式の上限を決め打ちにすることができ、いま頂点の番号などは気にしなくても良いのでAからの最短距離を保存した配列dをソートしてR倍した配列に対して、二分探索を適用することで上の条件式をみたす個数を計算することができ、Cの個数を数え上げられる。この動作は各頂点AにたいしてO(nlog(n))で可能であるから、十分間に合う。

そして、二分探索について、このように不等号にイコールがないときにはupper_boundを使うようにするとよさそう。この辺の使いどころがまだ慣れていなくて、かなり苦労した。また、Aからの最短距離を保存した配列dには全ての頂点ぶんが当然保存されているわけだが、A,B,Cはそれぞれ異なる頂点でなくてはならない。まず配列dをソートすると必ず先頭には自分自身Aとの距離がくるのでそれを除外する。そして、条件式 d(C)*R \lt d(B)*Tに注目すると、仮に R \lt TだとBCが一致してしまう場合も数えるべき部分に入ってしまうので、このあたりを考慮して数え上げる必要がある。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

const int INF=1000000000;

struct edge{int to,cost;};
//fi:最短距離 sc:頂点番号
typedef pair<int,int> P;

//隣接グラフ
std::vector<edge> G[2500];

int main(int argc, char const *argv[]) {
  int i,j;

  //input
  int n,m,r,t;
  scanf(" %d %d %d %d",&n,&m,&r,&t);
  rep(i,m){
    int x,y,z;
    scanf(" %d %d %d",&x,&y,&z);
    --x;
    --y;
    G[x].pb(edge{y,z});
    G[y].pb(edge{x,z});
  }

  long ans=0;

  //目的地Aを固定
  rep(i,n){
    //iからの距離
    int d[2500];
    fill(d,d+n,INF);
    d[i]=0;

    //dijkstra
    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P(0,i));
    while(!que.empty()){
      P p=que.top();
      que.pop();
      int v=p.sc;

      if(d[v]<p.first) continue;

      rep(j,G[v].size()){
        edge e=G[v][j];
        if(d[e.to]>d[v]+e.cost){
          d[e.to]=d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }

    //カメの方が先につくためには、d[c]/t<d[b]/r
    //つまりd[c]*r<d[b]*t

    //r倍
    int dr[2500];
    rep(j,n) dr[j]=d[j]*r;
    sort(dr,dr+n);

    //rep(j,n) printf("dr[%d]=%d\n",j,dr[j]);

    //ウサギのスタート地点Bを固定した時、
    rep(j,n){
      if(i==j) continue;
      /*
      printf(" now i:%d,j:%d\n",i,j);
      printf("d[%d]*%d=%d\n",j,t,d[j]*t);
      */
      int ct = upper_bound(dr,dr+n,d[j]*t-1)-dr;

      //printf("ct=%d\n", ct);

      if(r<t) --ct;
      ans+=ct-1;
    }
  }

  std::cout << ans << std::endl;
  return 0;
}