Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-11-26

SRM453.5 Div1 Easy: MazeMaker

01:23 | SRM453.5 Div1 Easy: MazeMaker - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM453.5 Div1 Easy: MazeMaker - naoya_t@topcoder SRM453.5 Div1 Easy: MazeMaker - naoya_t@topcoder のブックマークコメント

  • 高々2500ノードで、各ノードからのarcは高々50本
  • ということで、dijkstraで解く方法
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class MazeMaker {
 public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
    int N=sz(maze), M=sz(maze[0]), NM=N*M, Z=sz(moveRow);

    vector<bool> ok(NM,false);
    rep(r,N)rep(c,M) if(maze[r][c]=='.') ok[M*r + c] = true;
    
    vector<vector<int> > ar(NM,vector<int>(NM,infty));
    int start = M*startRow + startCol;

    rep(ri,N)rep(ci,M){
      int i = M*ri + ci; if (!ok[i]) continue;
      rep(z,Z){
        int rj=ri+moveRow[z], cj=ci+moveCol[z];
        if(0<=rj && rj<N && 0<=cj && cj<M){
          int j = M*rj + cj; ar[i][j]=1;
        }
      }
    }

    pair<vector<int>,vector<int> > res = dijkstra_all(ar, start);
    vector<int> distances = res.first;
    int dmax=0;
    rep(i,NM){
      if (i==start || !ok[i]) continue;
      int d=distances[i]; if (d==infty) return -1;
      if (d>dmax) dmax=d;
    }
    return dmax;
  }
};
  • dijkstraはスタート地点から他の全ノードへの距離を求めるやつ
  • predecessor返してるけど使わない(ので消してもいい)
const int infty = INT_MAX;

template <typename T> T infsum(T a, T b){
  return (a == infty || b == infty)? infty : (a + b);
}

template <typename T> pair<vector<T>,vector<int> >
dijkstra_all(const vector<vector<T> >& arclength, int start_v)
{
  int N = arclength.size();

  set<int> S;
  vector<T> distance(N, infty); // inftyは適当な大きな数
  vector<int> predecessor(N, -1);

  S.insert(start_v);
  distance[start_v] = 0;

  rep(v,N){
    if (v == start_v) continue;
    if (arclength[start_v][v] == infty) continue;
    
    distance[v] = arclength[start_v][v];
    predecessor[v] = start_v;
  }

  while (S.size() < N) { // 各点へ
    // find v* from V¥S with distance(v*) = min{distance(v):v from V¥S}
    int v_ = -1;
    T d_ = infty;
    rep(v,N){
      if (found(S,v)) continue;
      if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
    }
    if (v_==-1) break;
    S.insert(v_);

    rep(v,N){ // FOR ALL v from V¥S DO
      if (found(S,v)) continue;
      T d_ = infsum(distance[v_], arclength[v_][v]);
      if (d_ < distance[v]) {
        distance[v] = d_;
        predecessor[v] = v_;
      }
    }
  }

  return make_pair(distance,predecessor);
}

SRM453.5

02:54 | SRM453.5 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM453.5 - naoya_t@topcoder SRM453.5 - naoya_t@topcoder のブックマークコメント

11.25.2009+

.5って何さ

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 MazeMaker o - failed 0
1 450 PlanarGraphShop 撃墜された - - -
1 1000 TheAlmostLuckyNumbers 間に合わず -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091126

2009-11-18

SRM453

02:50 | SRM453 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM453 - naoya_t@topcoder SRM453 - naoya_t@topcoder のブックマークコメント

gdgd回。Matchの最中にTopCoderのサーバ落ちた!ノーゲーム。

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 TheBasketballDivOne o - o -
1 500 TheTournamentDivOne o - failed -
1 1000 TheSoccerDivOne 開いただけ -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091118

2009-11-05

SRM452

23:04 | SRM452 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM452 - naoya_t@topcoder SRM452 - naoya_t@topcoder のブックマークコメント

11.05.2009

cafelier先生と同じ部屋

続きを読む

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 NotTwo o - passed 227.51
1 500 IOIString 間に合わず - - -
1 1000 IncreasingNumber 間に合わず -
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091105