Google Code Jam 2009に登録してみた

60時間ぐらいでモンハン３にも満足して、オンラインの無料期間も終わったので少しクールダウン。
誰かに誘われるまでは、オフでも進めよう。

さて、アルゴリズムは門外漢なのだけれど、Code Jam 2009に登録してしまった。
C++の勉強になればいいなということでやってみる。
まずは過去問から。

2008年も過去問で一番古いやつから、Alien Numbers。

Alien Numbers
http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGIP6AQw

以下、解答含むネタばれ。
（過去問でも解答公開したらまずいんだろうか？？）

この問題は最初だけあってやることはとても簡単。
任意の基数で基数変換やるだけ。
でも、C++の標準ライブラリやら、変換アルゴリズム調べたりしてたら、時間かかってしまった。
そもそも、調べてやってるようではダメなんだろうけど。

// Alien Numbers


#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

#include <stdlib.h>
#include <math.h>


using namespace std;


const string
translate(const string& alienNumber, const string& sourceLang, const string& targetLang) {
	const int sourceRadix = sourceLang.length();
	const int targetRadix = targetLang.length();

	int alienNumberBinary = 0;
	for (int i = alienNumber.length() - 1, j = 0; 0 <= i; --i, ++j) {
		alienNumberBinary += sourceLang.find_first_of(alienNumber[i]) * pow(sourceRadix, j);
	}

	stringstream targetNumberStream;
	while (alienNumberBinary >= 1) {
		targetNumberStream << targetLang[alienNumberBinary % targetRadix];
		alienNumberBinary /= targetRadix;
	}

	string targetNumber = targetNumberStream.str();
	reverse(targetNumber.begin(), targetNumber.end());

	return targetNumber;
}


int main() {
	int maxLineNumber;
	string alienNumber, sourceLang, targetLang;

	cin >> maxLineNumber;

	for (int i = 0; i < maxLineNumber; ++i) {
		cin >> alienNumber >> sourceLang >> targetLang;
		cout << "Case #" << i + 1 << ": " << translate(alienNumber, sourceLang, targetLang) << endl;
	}

	return 0;
}

一応、Large datasetのほうでもちゃんと動作します。
添削してくれたりする人はいないかな。
C++的にはこうすべき、みたいなのが聞いてみたいが過疎ブログなので期待薄。