SRM451Div2

250

class ReverseMagicalSource {
public:
  int find(int source, int A) {

    int    sum = 0;
    while( sum <= A ){
      sum += source;
      source *= 10;
    }
    return sum;
  }
};

500

class BoredPhilosophers {
public:
  vector <int> simulate(vector <string> text, int N) {

    vector<string> v;
    {
      string s;
      for(int i=0; i<text.size(); ++i){
    s += text[i];
      }
      istringstream iss( s );
      while( iss >> s )v.push_back( s );
    }


    vector<int> ret;

    for(int i=0; i<N; ++i){
      set<string> cnt;
      for(int j=0; j+i<v.size(); ++j){
        string s;
        for(int k=0; k<=i; ++k){
          if(k)    s += ' ';
          s += v[j+k];
        }
        cnt.insert( s );
      }
      ret.push_back( cnt.size() );
    }

    return ret;
  }
};

1000
TopCoderにしては実装が重い気がした。

const int inf = 1 << 24;

struct Edge{
  int src, dst, cost;
  Edge(int s, int d, int c) : src(s), dst(d), cost(c) {}
};

const int H = 50;
const int W = 50;
const int N = H * W;
int no[H][W];

vector<Edge> g[N];
int dist[N];

struct State{
  int node, cost;
  State(int n, int c) : node(n), cost(c) {}
};
bool operator < (const State &a, const State &b)
{
  if( a.cost != b.cost )return a.cost > b.cost;
  return a.node < b.node;
}

void sssp(const int size, int src)
{
  priority_queue<State> q;
  bool vis[size];
  fill( vis, vis + size, false );
  fill( dist, dist + size, inf );
  for(q.push(State(src, 0)); q.size(); ){
    State s = q.top();
    q.pop();
    if( vis[s.node] )continue;
    vis[s.node] = true;
    dist[s.node] = s.cost;
    for(int i=0; i<g[s.node].size(); ++i){
      Edge e = g[s.node][i];
      if( vis[e.dst] )continue;
      q.push(State(e.dst, s.cost + e.cost));
    }
  }
  return ;
}

int deliver(vector<int> dst, int src)
{
  const int BIT = 1 << dst.size();
  int mn = inf;

  for(int bit = 0; bit < BIT; ++bit){
    int a = 0;
    int b = 0;
    int mx_a = 0;
    int mx_b = 0;
    for(int i=0; i<dst.size(); ++i){
      if( bit & (1 << i) ){
        mx_a = max( mx_a, dist[ dst[i] ] );
        a += dist[ dst[i] ] * 2;
      }
      else{
        mx_b = max( mx_b, dist[ dst[i] ] );
        b += dist[ dst[i] ] * 2;
      }
    }
    mn = min( mn, max(a - mx_a, b - mx_b) );
  }

  return mn;
}

class PizzaDelivery {
public:
  int deliverAll(vector <string> terrain) {

    const int h = terrain.size();
    const int w = terrain[0].size();

    vector<int> dst;
    int src;

    int size = 0;
    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        no[i][j] = size++;
        if( terrain[i][j] == '$' )dst.push_back( no[i][j] );
        else if( terrain[i][j] == 'X' ) src = no[i][j];
      }
    }

    fill( g, g + size, vector<Edge>() );

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        const int di[] = {0, 0, -1, 1};
        const int dj[] = {-1, 1, 0, 0};
        for(int d=0; d<4; ++d){
          int ni = i + di[d];
          int nj = j + dj[d];
          if( ni < 0 || nj < 0 )continue;
          if( h <= ni || w <= nj )continue;
          if( terrain[i][j] == '$' || terrain[ni][nj] == '$' ){
            g[ no[i][j] ].push_back( Edge( no[i][j], no[ni][nj], 2 ) );
            g[ no[ni][nj] ].push_back( Edge( no[ni][nj], no[i][j], 2 ) );
          }
          else if( terrain[i][j] == 'X' || terrain[ni][nj] == 'X' ){
            g[ no[i][j] ].push_back( Edge( no[i][j], no[ni][nj], 2 ) );
            g[ no[ni][nj] ].push_back( Edge( no[ni][nj], no[i][j], 2 ) );
          }
          else if( abs( terrain[i][j] - terrain[ni][nj] ) <= 1 ){
            int cost = 1 + ( terrain[i][j] != terrain[ni][nj] ) * 2;
            g[ no[i][j] ].push_back( Edge( no[i][j], no[ni][nj], cost ) );
            g[ no[ni][nj] ].push_back( Edge( no[ni][nj], no[i][j], cost ) );
          }
        }
      }
    }

    sssp(size, src);
    int ret = deliver(dst, src);
    return ret == inf ? -1 : ret;
  }
};