Google Code Jam

Qualification Roundが終わりました。このラウンドは問題が3問でて、どれか1問でもクリアすれば次のラウンドへ進めます。次に進める人数に制限はありません。また制限時間も24時間で、その間ならいつでも参加できます。

結果は、score: 76, Rank: 3126 でした。次のラウンドには進めるようなんですが、問題Cのラージが間違っていました。終了後は他の人のコードが見れたと思うんで、復習しないと…

以下、長ったらしいですが、コードをさらしてみます。言語はc++です。

A: Alien Language

腕ならし的な一問目。本質的な部分のアルゴリズムはなんてことないんですが、慣れの問題や、必要以上に慎重になりすぎたりで、時間がかかっちゃいました。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

vector  split(const string _s, const string del)
{
  vector  ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

vector  getWords(string s)
{
  vector  ret;
  bool inParen = false;
  string tmp;

  for (int i=0; iif (inParen)
{
  if (s[i] == '(')
    {
      cout << "Unexpected characotr" << endl;
      exit(-1);
    }
  else if (s[i] == ')')
    {
      ret.push_back(tmp);
      inParen = false;
      tmp.clear();
    }
  else
    {
      tmp += s[i];
    }
}
      else
{
  if (s[i] == '(')
    {
      inParen = true;
      tmp.clear();
    }
  else if (s[i] == ')')
    {
      cout << "Unexpected characotr" << endl;
      exit(-1);
    }
  else
    {
      tmp = s[i];
      ret.push_back(tmp);
      tmp.clear();
    }
}
    }

  return ret;
}

int match(vector  & words, vector  & dictionary)
{
  int ret = 0;

  for (int i=0; ibool ok = true;

      for (int j=0; jif (words[j].find(dictionary[i][j]) == string::npos)
  {
    ok = false;
    break;
  }

      if (ok)
ret++;
    }

  return ret;
}

int main(int argc, char ** argv)
{
  string line;
  ifstream file (argv[1]);
  int wordNum = 0;
  int dicNum = 0;
  int testNum = 0;
  vector  dictionary;

  vector  firstLine;
  getline(file, line);
  firstLine = split(line, " ");
  wordNum = toInt(firstLine[0]);
  dicNum = toInt(firstLine[1]);
  testNum = toInt(firstLine[2]);

  for (int i=0; ifor (int i=0; iint matches = 0;
      vector  words;
      getline(file, line);

      words = getWords(line);

      if (words.size() != wordNum)
{
  cout << "Word number is wrong" << endl;
  return -1;
}

      matches = match(words, dictionary);
      
      cout << "Case #" << i+1 << ": " << matches << endl;
    }

  return 0;
}

B: Watersheds

今度は実装力が問われる問題。アルゴリズムとしては、まずsinkなセルを探す、sinkのまわり4方向を調べ、真ん中のセルに水が流れ込んでいるセルは同じラベルとしてラベル付けする（このときのラベルは整数でつけてます）。この処理を再帰的に繰り返し、全体をラベリング。最後に全体を左上から操作し、ラベルを正しいアルファベット順につけ直す、というアプローチをとりました。

スモールのインプットで一度間違えてしまいました。原因は、一カ所rowとcolumnを逆にしている部分があり、tieのときの優先順位（北西東南）が異なってしまっていたためでした。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

vector  split(const string _s, const string del)
{
  vector  ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

char dirx[4] = {-1, 0, 0, 1};
char diry[4] = {0, -1, 1, 0};

vector int> > attrs;
int label[101][101];

bool inRange(int x, int y)
{
  bool ret = false;
  int row = attrs.size();
  int col = attrs[0].size();

  if (0 <= x && x < row && 0 <= y && y < col)
    ret = true;

  return ret;
}

vector int, int> > getSink(vector int> > attrs)
{
  vector int, int> > ret;

  for (int x=0; xfor (int y=0; ybool isSink = true;
for (int i=0; i<4; i++)
  if (inRange(x + dirx[i], y + diry[i]) &&
      attrs[x][y] > attrs[x+dirx[i]][y+diry[i]])
    {
      isSink = false;
      break;
    }
if (isSink)
  ret.push_back(make_pair(x, y));
      }

  return ret;
}

pair <int, int> flowTo(int x, int y)
{
  pair <int, int> ret = make_pair(x, y);
  int minAttr = attrs[x][y];

  for (int i=0; i<4; i++)
    {
      int dx = x + dirx[i];
      int dy = y + diry[i];
      if (inRange(dx, dy))
if (attrs[dx][dy] < minAttr)
  {
    ret = make_pair(dx, dy);
    minAttr = attrs[dx][dy];
  }
    }

  return ret;
}

int s(int x, int y, int labelnum)
{
  for (int i=0; i<4; i++)
    if (inRange(x + dirx[i], y + diry[i]))
      if (flowTo(x+dirx[i], y+diry[i]) == make_pair(x, y))
{
  if (label[x+dirx[i]], y+diry[i] != -1)
    label[x+dirx[i]][y+diry[i]] = labelnum;
  s(x+dirx[i], y+diry[i], labelnum);
}

  return 0;
}

vector  labeling(void)
{
  vector  ret;
  int alpCounter = 0;
  char label2alphabet[26];
  memset(label2alphabet, -1, sizeof(label2alphabet));

  for (int x=0; xfor (int y=0; yif (label2alphabet[label[x][y]] == -1)
    label2alphabet[label[x][y]] = 'a' + alpCounter++;
  row += label2alphabet[label[x][y]];
  row += " ";
}
      row.erase(row.end()-1);
      ret.push_back(row);
    }

  return ret;
}

vector  labelBasin(vector  in)
{
  attrs.clear();
  memset(label, -1, sizeof(label));
  vector  ret;
  vector int, int> > sinks;

  for (int i=0; i tmp;
      vector <int> rows;

      tmp = split(in[i], " ");

      for (int j=0; jfor (int i=0; ireturn ret;
}

int main(int argc, char ** argv)
{
  string line;
  ifstream file (argv[1]);
  int mapNum = 0;

  vector  firstLine;
  getline(file, line);
  mapNum = toInt(line);

  for (int mi=0; mi s;
      int row, column;
      vector  inputMap;
      vector  outputMap;

      getline(file, line);
      s = split(line, " ");
      row = toInt(s[0]);
      column = toInt(s[1]);

      for (int i=0; i"Case #" << mi+1 << ":" << endl;
      for (int i=0; ireturn 0;
}

C: Welcome To Code Jam

今度は分割統治（再帰?, メモ化?, あんまり自身無いです）の問題。問題の意図を理解するのに時間がかかってしまいました。再帰とメモ化の部分がすんなり書けて、個人的には満足です。

計算結果が巨大になるので、それをどう扱おうかというところで少し悩みました。とりあえずコード中ではdoubleで計算結果を持ち回して、出力するときにsprintfを使う方法で実装しました。

large inputでincorrectだったので、どこかに見落としがあるようです。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}

vector  split(const string _s, const string del)
{
  vector  ret;
  string s = _s;

  while (!s.empty())
    {
      size_t pos = s.find(del);
      string sub = "";
      sub = s.substr(0, pos);
      ret.push_back(sub);
      if (pos != string::npos)
pos += del.size();
      s.erase(0, pos);
    }

  return ret;
}

string welcome = "welcome to code jam";
string paragpeph;
double memo[501][20];

double r(int iParagraph, int iWelcome)
{
  double ret = 0.0;

  if (memo[iParagraph][iWelcome] != -1.0)
    return memo[iParagraph][iWelcome];

  for (int i=iParagraph; iif (paragpeph[i] == welcome[iWelcome])
      if (iWelcome == welcome.size()-1)
ret+=1.0;
      else
ret += r(i+1, iWelcome+1);

  memo[iParagraph][iWelcome] = ret;
    
  return ret;
}

string getResult(double d)
{
  string ret(4, '0');
  char c[1000];
  string cs;

  sprintf(c, "%.0f", d);
  cs = c;

  for (int i=0; i4; i++)
    ret[3-i] = cs[cs.size()-1-i];

  return ret;
}

string getCount(string s)
{
  string ret;
  double count;
  paragpeph = s;
  for (int i=0; i<501; i++)
    for (int j=0; j<20; j++)
      memo[i][j] = -1;

  count = r(0, 0);

  ret = getResult(count);

  return ret;
}

int main(int argc, char ** argv)
{
  string line;
  ifstream file (argv[1]);
  int problemNum = 0;

  vector  firstLine;
  getline(file, line);
  problemNum = toInt(line);

  for (int pi=0; pi"Case #" << pi+1 << ": " << ret << endl;
    }

  return 0;
}

Google Code Jam

Google Code JamのQualification Roundを解答し終えました。なんとか3問とも解答できました。しかしかなり時間がかかってしまい、全体で3時間半くらいいっちゃいました。次からは制限時間つきなので、スピードアップしなければ…

とりあえず、毎回最初に同じコードをコピペしちゃってるので、スケルトンみたいなやつを生成するスクリプトでも書こうかなと思います。できれば、topcoderのプラグインみたいに、テストを走らせることができたら最高ですね。

コードはこのラウンドが完全に終了してからさらしたいと思います。