Google Code Jam

Round1 A終わりましたが、解けたのは問題Aのスモールのみというひどい内容。Rankは1354。今日の夜もがんばろう。

gcj全体のコードはこちら。

cou929’s gcj2009 at master - GitHub

A. Multi-base happiness

書くのに1時間以上かかった。問題を理解するところと、細かいバグ取りに時間を取られたかんじ。

アルゴリズムとしても、普通に総当たりで解いているので、ラージインプットは余裕で間に合わず。

vector  split(const string _s, const string del);
int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
string toStr(int n) {ostringstream ss; ss << n; return ss.str();}


map int, int>, bool> memo;

vector <int> cnv(const int n, const int base)
{
  vector <int> ret;
  int num = n;

while (num >= base)
    {
      ret.push_back(num%base);
      num /= base;
    }

ret.push_back(num);

return ret;
}

bool happy(const int n, const int base)
{
  bool ret = false;
  int num = n;
  set <int> past;

while (1)
    {
      //      cout << num << endl;;
      past.insert(num);
      vector <int> elems = cnv(num, base);
      int sum = 0;
      for (unsigned int i=0; i//      cout << “sum: ” << sum << endl;

  <span class="synStatement">if</span> (sum == <span class="synConstant">1</span> || (memo.find(make_pair(sum, base)) != memo.end() && memo[make_pair(sum, base)]))


{
  ret = true;
  past.insert(sum);

for (set <int>::iterator it=past.begin(); it!=past.end(); it++)
    memo[make_pair(*it, base)] = true;

break;
}
      else if ((memo.find(make_pair(sum, base)) != memo.end() && !memo[make_pair(sum, base)]) ||
       past.find(sum) != past.end())
{
  past.insert(sum);
  for (set <int>::iterator it=past.begin(); it!=past.end(); it++)
    memo[make_pair(*it, base)] = false;

break;
}

  num = sum;
}


return ret;
}

string run(string inputs)
{
  string ret;
  vector  st;
  vector <int> bases;

st = split(inputs, ” “);
  for (unsigned int i=0; i

int i = 2;

while (1)
    {
      bool isHappy = true;
      for (unsigned int j=0; jif ((memo.find(make_pair(i, bases[j])) != memo.end() && !memo[make_pair(i, bases[j])]) ||
      !happy(i, bases[j]))
    {
      isHappy = false;
      break;
    }
}

  <span class="synStatement">if</span> (isHappy)


{
  ret = toStr(i);
  break;
}

  i++;
}


return ret;
}

int main(int argc, char ** argv)
{
  if (argc != 2)
  {
    cout << “Usage “ << argv[0] << ” \n“;
    return 0;
  }

ifstream file (argv[1]);
  string line;
  vector  tmp;
  vector <int> args;

getline(file, line);
  tmp = split(line, ” “);
  for (unsigned int i=0; i

for (int lineNum = 0; lineNum0]; lineNum++)
    {
      string result;

  getline(file, line);

  result = run(line);

  cout << <span class="synConstant">"Case #"</span> << lineNum+<span class="synConstant">1</span> << <span class="synConstant">": "</span> << result << endl;
}


return 0;
}

B. Crossing the Road

幅優先探索で実装、テストケースは通ったけど、スモールでさえincorrectだった。うーむ。信号をわたるときの時間の算出が自信ないです。

たぶんグラフにして考えれば良かったんじゃないか。ダイクストラ法くらいはできるようにしとかなきゃ。

#define MOVE_LEFT 0
#define MOVE_TOP 1


vector <int> inters[20][20];

int waitInter(pair <int, int> curPos, int minute, int dir)
{
  int ret = 0;

int x = curPos.first / 2;
  int y = curPos.second / 2;

int n = inters[x][y][0];
  int e = inters[x][y][1];
  int t = inters[x][y][2];

int curTIme = abs(t - minute);
  int mod = curTIme%(n+e);

if (dir == MOVE_LEFT)
    {
      if (mod < n)
ret = n - mod - 1;
      else
ret = 0;
    }
  else
    {
      if (mod < n)
ret = 0;
      else
ret = mod - n + 2;
    }
  return ret;
}

int moveRight(pair <int, int> curPos, int minute)
{
  int ret = 0;

if (curPos.second % 2 == 0)
    ret = waitInter(curPos, minute, MOVE_LEFT) + 1;
  else
    ret = 2;

return ret;
}

int moveTop(pair <int, int> curPos, int minute)
{
  int ret = 0;

if (curPos.first % 2 == 0)
    ret = 2;
  else
    ret = waitInter(curPos, minute, MOVE_TOP) + 1;

return ret;
}

string run(int N, int M)
{
  string ret = “0”;

//   cout << N << “ ” << M << endl;
//   for (int i=0; i
//     for (int j=0; j
//       cout << i << “, ” << j << “: ” << inters[i][j][0] << “ ” << inters[i][j][1] << “ ” << inters[i][j][2] << endl;

pair <int, int> start = make_pair(N2-1, 0);
  pair <int, int> goal = make_pair(0, M2-1);
  queue int, int>, int> > q;
  int time[N2][M2];
  for (int i=0; i2; i++)
    for (int j=0; j2; j++)
      time[i][j] = 2000000000;

int tt = 2000000000;

q.push(make_pair(start, 0));

while (!q.empty())
    {
      pair <int, int> curPos;
      int minute;
      pair int, int>, int> t;

  t = q.front();
  q.pop();

  curPos = t.first;
  minute = t.second;


//       if (time[curPos.first][curPos.second] > minute)
// 	time[curPos.first][curPos.second] = minute;
//       else
// 	continue;

  <span class="synStatement">if</span> (curPos == goal)


tt = min(tt, minute);

  <span class="synComment">//      cout << curPos.first << ", " << curPos.second << ": " << minute << endl;</span>

  <span class="synStatement">if</span> (curPos.second+<span class="synConstant">1</span> < M*<span class="synConstant">2</span>)


q.push(make_pair(make_pair(curPos.first, curPos.second+1), minute + moveRight(curPos, minute)));
      if (curPos.first-1 >= 0)
q.push(make_pair(make_pair(curPos.first-1, curPos.second), minute + moveTop(curPos, minute)));
    }

//  ret = toStr(time[goal.first][goal.second]);
  ret = toStr(tt);

return ret;
}

int main(int argc, char ** argv)
{
  if (argc != 2)
    {
      cout << “Usage “ << argv[0] << ” \n“;
      return 0;
    }

ifstream file (argv[1]);
  string line;
  vector  tmp;
  vector <int> args;

getline(file, line);
  tmp = split(line, ” “);
  for (unsigned int i=0; i

for (int lineNum = 0; lineNum0]; lineNum++)
    {
      string result;
      string road, inter;

  getline(file, road);
  vector <string> roadt = split(road, <span class="synConstant">" "</span>);
  <span class="synType">int</span> N = toInt(roadt[<span class="synConstant">0</span>]);
  <span class="synType">int</span> M = toInt(roadt[<span class="synConstant">1</span>]);

  <span class="synStatement">for</span> (<span class="synType">int</span> i=<span class="synConstant">0</span>; i<N; i++)


{
  getline(file, inter);
  vector  intert;
  intert = split(inter, ” “);
  for (int j=0; jint> tmp;
      tmp.push_back(toInt(intert[j3+0]));
      tmp.push_back(toInt(intert[j3+1]));
      tmp.push_back(toInt(intert[j*3+2]));
      inters[i][j] = tmp;
    }
}

  result = run(N, M);

  cout << <span class="synConstant">"Case #"</span> << lineNum+<span class="synConstant">1</span> << <span class="synConstant">": "</span> << result << endl;
}


return 0;
}

C. Collecting Cards

問題読んだだけ。全然時間なかった。

Round1 A 感想

スコアボードを見てみると、45分くらいで問題Aのスモールだけ解いている人でも1000位以内にはいっていた。よって次からは、全問とこうとはせず、問題Aだけとか各問題のスモールだけでもいいんで、しっかり解こうという方針でいきます。

あとは細かいことでも時間の節約できそうなことはやっておこう。とりあえず入力を解析するのに使っているsplit()関数を改良。引数のstringを分割するためのデリミタをデフォルトで空白(” “)にするのと、vector を返すバージョン（今までは vector <string> を返していた）を新たに作った。

vector <int> split(const string _s, const string del = " ");

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

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

  return ret;
}

ところで、場合に応じて返り値の型を変えるような関数って、CとかC++じゃ実現できないのかな。たとえば上の関数の場合、返り値がvector バージョンと、vector バージョンの2つがあるけれど、コードの中身はほぼ同じ。今は返り値の型に応じて別の関数を作っている。あとで調べよう。

perlでのSTDOUTのフラッシュ

ftp経由でサーバにアクセスしてファイルを編集する書き捨てperlスクリプト - フリーフォーム フリークアウト

以前こちらの記事で、perlで標準出力のバッファをフラッシュする方法がないかなと思っていたところ、id:shagさんに教えていただきました！

use IO::Handle;
STDOUT->autoflush(1);
か
local $| = 1;

このように、IO::HandleをuseしてSTDOUT->autoflush(1);というふうにするか、特殊変数$|(|は1ではなく縦棒)に0以外の値を設定すると、バッファがprintやwriteするごとにオートフラッシュされるようになります。

詳しくは、perldocのperlvarに書かれています。

perlvar - perldoc.perl.org