TCO2011 Qual3

参加記録。

250
Failed System Test

500

 class CoinMachinesGame {
public:
  int maxGames(int c, vector <int> need, vector <int> give) {
    int cnt = 0;

    while( true ){
      int tmp = c;

      const int size = need.size();
      int idx = 0;
      int mx = -(1 << 30 );
      for(int i=0; i<size; ++i){
        if( need[i] <= c ){
          if( mx < give[i] - need[i] ){
            idx = i;
            mx = give[i] - need[i];
          }
        }
      }

      int game = c / need[idx];
      c -= need[idx] * game;
      c += give[idx] * game;
      cnt += game;

      if( tmp == c )break;
    }

    return cnt;
  }
}; 

1000

class ComplementMachine2D {
public:
  int largestSubmatrix(vector <string> m) {

    int r = max( m.size(), m[0].size() );

    for(int begin=0; begin < m[0].size(); ++begin){
      for(int end = begin+1; end <= m[0].size(); ++end){

        for(int top = 0; top < m.size(); ++top){
          for(int bottom = top + 1; bottom <= m.size(); ++bottom){

            bool a, b;
            a = true;
            b = true;

            for(int i=begin; i<end; ++i){
              a = a && m[top][i] == m[bottom-1][i];
              b = b && m[top][i] != m[bottom-1][i];
            }

            if( !a && !b )break;

            r = max( r, (bottom - top) * (end - begin) );
          }
        }
      }
    }
    return r;
  }
};

---

250再挑戦
個数が多くて6個で、数値の範囲が1-15と小さいので、充分大きい数まで試せばいい。

class AllButOneDivisor {
public:
  int getMinimum(vector <int> v) {
    for(int n = 1; n < 100000; ++n){
      int cnt = 0;
      for(int i=0; i<v.size(); ++i){
        if( n % v[i] == 0 ) ++cnt;
      }
      if( cnt+1 == v.size() )return n;
    }
    return -1;
  }
};