Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2012-01-30

Facebook Hacker Cup 2012 Round 1 22:02 Facebook Hacker Cup 2012 Round 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2012 Round 1 - nodchipのTopCoder日記 Facebook Hacker Cup 2012 Round 1 - nodchipのTopCoder日記 のブックマークコメント

Checkpoint

  • 問題を整理すると{}_{n}C_{k}*{}_{n'}C_{k'}=Sを満たしながらT=n+n'を最小化しろということだと思う
  • まずは素因数分解ルーチンを書く
  • そして約数列挙ルーチンを書く
  • 約数の数はそんなに多くないはずなので愚直に書けば良いと思う
  • 最後に[tex:{}_{n}C_{k}=t}を満たすような最小のnを求めるルーチンを書いておしまいだと思う・・・
  • Submit -> Wrong Answer
  • orz

Recover the Sequence

  • この手の問題は貪欲法で解ける気がする
  • まずどの1/2がどの再帰関数呼び出しに相当するのかを調べる
  • 続いて入力の後ろからarr1とarr2に振り分けていく
  • Submit -> Accepted
string input;
int inputIndex;
typedef pair<int, int> Range;
struct Block {
	Range arr;
	Range input;
};
vector<Block> blocks;

Range merge(Range range1, Range range2);
Range mergeSort(Range range) {
	int n = range.second - range.first;
	if (n <= 1) {
		return range;
	}

	int mid = n / 2;
    
	Range firstHalf = mergeSort(Range(range.first, range.first + mid));
	Range secondHalf = mergeSort(Range(range.first + mid, range.second));
    return merge(firstHalf, secondHalf);
}

Range merge(Range range1, Range range2) {
	assert(range1.first <= range1.second);
	assert(range1.second == range2.first);
	assert(range2.first <= range2.second);
	assert(range1.first < range2.second);

	blocks.push_back(Block());
	Block& b = blocks.back();
	b.arr = Range(range1.first, range2.second);
	b.input.first = inputIndex;

	int left = range1.first;
	int length = range2.second - range1.first;

	while (range1.first < range1.second && range2.first < range2.second) {
		if (input[inputIndex++] == '1') {
			++range1.first;
		} else {
			++range2.first;
		}
	}
	assert(range1.first == range1.second || range2.first == range2.second);

	b.input.second = inputIndex;

	return Range(left, left + length);
}

int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	REP(t, T) {
		inputIndex = 0;
		blocks.clear();

		int N;
		cin >> N >> input;

		mergeSort(Range(0, N));

		// Restore
		vector<int> v;
		REP(i, N) {
			v.push_back(i + 1);
		}

		for (vector<Block>::reverse_iterator rit = blocks.rbegin(), ritEnd = blocks.rend(); rit != ritEnd; ++rit) {
			const Block& b = *rit;
			vector<int> arr1, arr2;
			vector<int>::iterator it = v.begin() + b.arr.first;
			for (int index = b.input.first; index < b.input.second; ++index) {
				if (input[index] == '1') {
					arr1.push_back(*it++);
				} else {
					arr2.push_back(*it++);
				}
			}

			assert(arr1.size() == (b.arr.second - b.arr.first) / 2 ||
				arr2.size() == (b.arr.second - b.arr.first) - (b.arr.second - b.arr.first) / 2);

			while (arr1.size() < (b.arr.second - b.arr.first) / 2) {
				arr1.push_back(*it++);
			}
			while (arr2.size() < (b.arr.second - b.arr.first) - (b.arr.second - b.arr.first) / 2) {
				arr2.push_back(*it++);
			}

			it = copy(ALL(arr1), v.begin() + b.arr.first);
			copy(ALL(arr2), it);
		}

		ll result = 1;
		REP(i, v.size()) {
			result = (31L * result + v[i]) % 1000003;
		}

		printf("Case #%d: %d\n", t + 1, (int)result);
	}
}

Squished Status

  • 先頭から配るDPをするだけ
  • と思ったら解答ファイルに負の値が入っていた!
  • 4207849484はintだと負の値になるらしい。
  • 急いで修正
  • Submit -> Accepted
int main() {
	std::ios::sync_with_stdio(false);

	int N;
	cin >> N;
	REP(n, N) {
		int M;
		cin >> M;
		string input;
		cin >> input;

		static ll dp[1024 * 1024];
		CLEAR(dp);
		dp[0] = 1;
		REP(i, input.size()) {
			if (input[i] == '0') {
				continue;
			}

			for (int j = 1; j <= 3 && i + j <= input.size(); ++j) {
				if (atoi(input.substr(i, j).c_str()) > M) {
					continue;
				}
				dp[i + j] += dp[i];
				dp[i + j] %= 4207849484LL;
			}
		}

		cout << "Case #" << n + 1 << ": " << dp[input.size()] << endl;
	}
}

結果

xoo 2問正解でRound 1敗退となりました。1ミスで落ちるのは辛いです・・・。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20120130
 |