SRM345Div2

250

class Trekking {
public:
  int findCamps(string trail, vector <string> plans) {

    const int inf = 1 << 24;
    int mn = inf;
    for(int i=0; i<plans.size(); ++i){
      if( trail.size() != plans[i].size() )continue;
      int cnt = 0;
      for(int j=0; j<trail.size(); ++j){
        if( trail[j] == '^' && plans[i][j] == 'C'){
          cnt = inf;
          break;
        }
        if( plans[i][j] == 'C' ) ++cnt;
      }
      mn = min( mn, cnt );
    }

    return mn == inf ? -1 : mn;
  }
};

500

class Pathfinding {
public:

  double dist(int ai, int aj, int bi, int bj){
    double s = ai - bi;
    double t = aj - bj;
    return sqrt( s * s + t * t );
  }

  int getDirections(int x, int y) {

    int ret = 0;
    int i, j;
    i = j = 0;

    while( !(i == x && j == y) ){

      int di = (j % 2) ? -1 : +1;
      int dj = (i % 2) ? -1 : +1;

      int ai = i + di, aj = j;
      int bi = i, bj = j + dj;

      double a = dist(ai, aj, x, y);
      double b = dist(bi, bj, x, y);
      if( a < b ){
        i = ai;
        j = aj;
      }
      else{
        i = bi;
        j = bj;
      }
      ++ret;
    }

    return ret;
  }
};

1000
detectSCCは強連結成分(Strongly Connected Component)の検出。コードは略。

class BikeRiding {
public:
  int countRoutes(vector <string> paths, vector <int> startPoints, int endPoint, int n) {

    const int N = 50 + 1;
    const int size = paths.size();

    bool g[N][N];
    fill( g[0], g[N], false );

    Graph graph(size);

    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        g[i][j] = paths[i][j] - '0';

        if( g[i][j] ) graph[i].push_back( Edge(i, j) );
      }
    }

    vector< vector<int> > scc = detectSCC( graph );

    bool taboo[size];
    fill( taboo, taboo + size, false );

    for(int i=0; i<scc.size(); ++i){
      if( scc[i].size() == 1 ) continue;
      for(int j=0; j<scc[i].size(); ++j){
        taboo[ scc[i][j] ] = true;
      }
    }
    for(int i=0; i<size; ++i){
      if( g[i][i] ) taboo[i] = true;
    }

    int t[N][N];
    fill( t[0], t[N], 0 );

    for(int i=0; i<startPoints.size(); ++i){
      t[0][ startPoints[i] ] = 1;
    }

    const int LIM = n + 1;
    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        if( t[i][j] == 0 )continue;
        for(int k=0; k<size; ++k){
          if( g[j][k] ){
            int tmp = t[i+1][k] + t[i][j];
            if( taboo[k] ) tmp = LIM;
            t[i+1][k] = min( tmp, LIM );
          }
        }
      }
    }

    int sum = 0;
    for(int i=0; i<size; ++i){
      sum = min( sum + t[i][ endPoint ], LIM );
    }
    
    return n < sum ? -1 : sum;
  }
};