SRM326Div2

250

class AdditionCycles {
public:
  int cycleLength(int n) {
    set<int> s;
    while( s.count(n) == 0 ){
      s.insert(n);
      n = n % 10 * 10 + (n / 10 + n % 10) % 10;     
    }
    return s.size();
  }
};

500
問題を読むのにだいぶ時間がかかった。

class PositiveID {
public:
  int maximumFacts(vector <string> s) {
    vector< vector<string> > g( s.size() );
    for(int i=0; i<s.size(); ++i){
      replace( s[i].begin(), s[i].end(), ',', ' ' );
      istringstream iss( s[i] );
      string t;
      while( iss >> t ) g[i].push_back(t);
    }
    
    int mx = 0;

    for(int i=0; i<g.size(); ++i){
      sort( g[i].begin(), g[i].end() );
    }

    for(int i=0; i<g.size(); ++i){
      for(int j=i+1; j<g.size(); ++j){
        int cnt = 0;
        for(int k=0; k<g[i].size(); ++k){
          cnt += binary_search( g[j].begin(), g[j].end(), g[i][k] );
        }
        mx = max(mx, cnt);
      }
    }

    return mx;
  }
};

1000

const int N = 50 + 1;
bool  vis[N][N];

int h, w;

int g[N][N];
int b[N][N];

const int di[] = {0, 0, -1, 1};
const int dj[] = {-1, 1, 0, 0};

bool rec(int i, int j, int lim)
{
  if( lim < g[i][j] )return false;
  vis[i][j] = true;
  bool flg = false;
  for(int d=0; d<4; ++d){
    int ni = i + di[d];
    int nj = j + dj[d];
    if(ni < 0 || nj < 0){
      flg = true;
      continue;
    }
    if(h <= ni || w <= nj){
      flg = true;
      continue;
    }
    if( vis[ni][nj] )continue;
    flg = flg || rec(ni, nj, lim);
  }
  return flg;
}

class PoolFiller {
public:
  int getCapacity(vector <string> l) {
    h = l.size();
    w = l[0].size();

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        g[i][j] = l[i][j] - '0';
      }
    }

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        for(int lim=1; lim<=10; ++lim){
          fill( &vis[0][0], &vis[N-1][N], false );
          if( rec(i, j, lim) ){
            b[i][j] = lim;
            break;
          }
        }
      }
    }

    int sum = 0;
    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        sum += b[i][j] - g[i][j];
      }
    }

    for(int i=0; i<h; ++i){
      for(int j=0; j<w; ++j){
        cout << b[i][j] << ' ';
      }
      cout << endl;
    }
   
    return sum;
  }
};