Google Code Jam 1C

Bの問題の文意が分かりにくいかもしれない．factor には因数という意味もあるので，"within a factor of C"は「C倍以内のスケールで」ということです．

Problem A - Rope Intranet の解法例

#include <iostream>
#include <vector>
using namespace std;

int solve(void)
{
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  for( int i = 0 ; i < N ; ++i ) {
    cin >> A[i] >> B[i];
  }

  int count = 0;
  for( int i = 0 ; i < N ; ++i ) {
    for( int j = i + 1 ; j < N ; ++j ) {
      if( (A[i] - A[j]) * (B[i] - B[j]) < 0 ) {
        ++count;
      }
    }
  }
  return count;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}

Problem B - Load Testing の解法例

#include <iostream>
#include <cmath>
using namespace std;
typedef long long int64;

int solve(void)
{
  int64 L, P, C;
  cin >> L >> P >> C;
  int count = 0;
  for( int64 l = L, p = P ; l * C < p ; ++count ) {
    double sqr = sqrt((double)l * p);
    int64 isqr = (int64)(sqr + .5);
    if( isqr < sqr ) l = isqr;
    else p = isqr;
  }
  return count;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}

Problem C - Making Chess Boards の解法例

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cctype>
using namespace std;

struct heap
{
  int siz, i, j;
  heap() : siz(0), i(-1), j(-1) {}
  heap(int a, int b, int c) : siz(a), i(b), j(c){}
};
bool operator<(const heap& a, const heap& b)
{
  if( a.siz < b.siz ) return true;
  if( a.siz > b.siz ) return false;
  if( a.i < b.i ) return true;
  if( a.i > b.i ) return false;
  return ( a.j < b.j );
}

template<class T>
inline T MAX(T a, T b){ return (a > b) ? a : b; }
template<class T>
inline T MIN(T a, T b){ return (a < b) ? a : b; }

inline void update(set<heap>& st, vector< vector<short> >& big, int i, int j, int val)
{
  if( big[i][j] > val ) {
    st.erase(st.find(heap(-big[i][j], i, j)));
    big[i][j] = val;
    st.insert(heap(-big[i][j], i, j));
  }
}

void solve(void)
{
  int M, N;
  cin >> M >> N;
  vector< vector<char> > board(M, vector<char>(N));
  for( int i = 0 ; i < M ; ++i ) {
    for( int j = 0 ; j < N ; j += 4 ) {
      char hex;
      cin >> hex;
      hex = isalpha(hex) ? (hex - 'A' + 10) : (hex - '0');
      board[i][j  ] = (hex & 8) >> 3;
      board[i][j+1] = (hex & 4) >> 2;
      board[i][j+2] = (hex & 2) >> 1;
      board[i][j+3] = hex & 1;
    }
  }

  vector< vector<short> > big(M, vector<short>(N, 1) );
  set<heap> st;
  st.insert(heap(-1, 0, 0));
  for( int i = 1 ; i < M ; ++i ) st.insert(heap(-1, i, 0));
  for( int j = 1 ; j < N ; ++j ) st.insert(heap(-1, 0, j));
  for( int i = 1 ; i < M ; ++i ) {
    for( int j = 1 ; j < N ; ++j ) {
      if( board[i  ][j-1] != board[i][j] &&
          board[i-1][j  ] != board[i][j] &&
          board[i-1][j-1] == board[i][j]    ) {
        big[i][j]   = big[i-1][j  ];
        big[i][j] <?= big[i-1][j-1];
        big[i][j] <?= big[i  ][j-1];
        ++big[i][j];
      } else {
        big[i][j] = 1;
      }
      st.insert(heap(-big[i][j], i, j));
    }
  }

  // Process;
  int nums[513][2];
  int numSize = 0;
  int siz = 1024;
  while( !st.empty() ) {
    set<heap>::iterator p = st.begin();
    int size   = -(p->siz);
    int bottom = p->i + 1;
    int right  = p->j + 1;
    int top    = bottom - size;
    int left   = right - size;

    // Erase largest chess board
    for( int i = top ; i < bottom ; ++i ) {
      for( int j = left ; j < right ; ++j ) {
        st.erase(st.find(heap(-big[i][j], i, j)));
        big[i][j] = 0;
      }
    }

    // Update related eliminated board
    const int imax = MIN(M, bottom + size);
    const int jmax = MIN(N, right  + size);
    for( int i = top ; i < bottom ; ++i ) {
      for( int j = right, dj = 1 ; j < jmax ; ++j, ++dj ) {
        update(st, big, i, j, dj);
      }
    }
    for( int i = bottom, di = 1 ; i < imax ; ++i, ++di ) {
      for( int j = left ; j < right ; ++j ) {
        update(st, big, i, j, di);
      }
    }
    for( int i = bottom, di = 1 ; i < imax ; ++i, ++di ) {
      for( int j = right, dj = 1 ; j < jmax ; ++j ,++dj ) {
        update(st, big, i, j, MAX(dj, di));
      }
    }

    if( size != siz ) {
      ++numSize;
      nums[numSize][0] = size;
      nums[numSize][1] = 1;
      siz = size;
    } else {
      ++nums[numSize][1];
    }
  }

  // Output
  cout << numSize <<"\n";
  for( int i = 1 ; i <= numSize ;++i ) {
    cout << nums[i][0] << " " << nums[i][1] << "\n";
  }
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cout << "Case #" << t << ": ";
    solve();
  }
}