Google Code Jam 1A

Problem A - Rotate の解答例

普通にやるんだったら右・下・右下・左下の4方向についてdx, dyを作ってやるのが楽だと思う．計算時間のオーダーどっちも O(N²K) だし，N,K≦50だし．方法が面白いので敢えてビット操作．以前見た情報処理学会会誌(2008年12月号／Vol.49 No.12)掲載の田浦先生版N-Queenの記憶を導きつつ．

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long uint64;

bool check(const int K, const vector<string>& str, const char c)
{
  const int N = str.size();
  vector<uint64> bit;

  // Convert & partial check
  for( int i = 0 ; i < N ; ++i ) {
    uint64 row = 0;
    for( int j = 0 ; j < N ; ++j ) {
      if( str[i][j] == '.' ) { continue; }
      row <<= 1;
      if( str[i][j] == c ) { row |= 1; }
    }
    bit.push_back(row);

    // Check HoRizontal
    uint64 hr = row;
    for( int j = 1 ; j < K ; ++j ) { hr = (hr << 1) & row; }
    if( hr ) { return true; }
  }

  // Check Vertically, Left-down diagonary, Right-down diagonary
  for( int i = 0 ; i <= N - K ; ++i ) {
    uint64 v, l, r;
    v = l = r = bit[i];
    for( int j = i + 1 ; j < i + K ; ++j ) {
      v &= bit[j];
      l = (l << 1) & bit[j];
      r = (r >> 1) & bit[j];
    }
    if( v | l | r ) { return true; }
  }

  return false;
}

string solve()
{
  int N, K;
  cin >> N >> K;
  vector<string> board(N);
  for( int i = 0 ; i < N ; ++i ) cin >> board[i];

  bool red  = check(K, board, 'R');
  bool blue = check(K, board, 'B');
  
  if( red && blue ) return string("Both");
  if( red ) return string("Red");
  if( blue ) return string("Blue");
  return string("Neither");
}

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

Problem B - Make it Smooth の解答例

1000*256 は何か理由があるわけじゃなくて，単純に大きな数です．十分大きければいいんだけど，INT_MAX とか使うとその後の加算でオーバーフローするので止めました．

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

int table[102][256];
int D, I, M, N;
int a[101];

void makeTable(void)
{
  for( int i = 0 ; i < 256 ; ++i ) {
    table[0][i] = 0;
  }

  for( int len = 0 ; len < N ; ++len ) {
    for( int last = 0 ; last < 256 ; ++last ) {
      // Try deleting
      int min = table[len][last] + D;

      // Try all values for the previous pixel value
      for( int i = 0 ; i < 256 ; ++i ) {
        int pre = table[len][i];
        int mov = abs(last - a[len]);
        int ins = (M) ? (((abs(last - i) - 1) / M) * I) : ( last == i ) ? 0 : (1000 * 256);
        ins = (ins < 0) ? 0 : ins;
        min = ( min < pre + mov + ins ) ? min : (pre + mov + ins);
      }
      table[len+1][last] = min;
    }
  }
}

int solve(void)
{
  // Input
  cin >> D >> I >> M >> N;
  for( int i = 0 ; i < N ; ++i ) { cin >> a[i]; }

  // Make information
  makeTable();

  // Search minimum
  int min = table[N][0];
  for( int i = 1 ; i < 256 ; ++i ) {
    min = (min < table[N][i]) ? min : table[N][i];
  }
  return min;
}

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 - Number Game の解答例

Analyticsにある通りの計算をしただけ．あと対称性からA≧φBだけじゃなくてφA≦Bもカウントするべし．

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

const double GOLD1 = (1 + sqrt(5.0)) * .5;
const double GOLD2 = 1.0 / GOLD1;

int64 solve(void)
{
  int64 A1, A2, B1, B2;
  cin >> A1 >> A2 >> B1 >> B2;
  int64 num = 0;
  for( int64 b = B1 ; b <= B2 ; ++b ) {
    int64 at1 = static_cast<int64>(b * GOLD1);
    int64 at2 = static_cast<int64>(b * GOLD2);
    if( at1 < A1 ) { num += A2 - A1 + 1; }
    else if( at1 < A2 ) { num += A2 - at1; }
    if( A2 <= at2 ) { num += A2 - A1 + 1; }
    else if( A1 <= at2 ) { num += at2 - A1 + 1; }
  }
  return num;
}

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;
}