ARC 025 C - ウサギとカメ

問題

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

アイデア

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

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

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

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

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

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

実装(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;
}