Hatena::Grouptopcoder

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

 | 

2009-10-21

Single Round Match 451 @ TopCoder 13:45 Single Round Match 451 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 451 @ TopCoder - nodchipのTopCoder日記 Single Round Match 451 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

Single Round Match 451 @ TopCoderCommentの参加記録です。

Easy 250 MagicalSource

ある数字を10倍しながら足して行った数字が与えられる。元の数字として条件を満たす数字のうち最小のものを求めよ。

1、11、111、・・・と順に割って、割り切れたら最小の値を更新するだけです。

class MagicalSource {
public:
	long long calculate(long long x) {
		long long result = 1LL << 62;
		ll a = 1;
		do {
			if (x % a == 0) {
				result = min(result, x / a);
			}
			a *= 10;
			++a;
		} while (a < 1LL << 60);

		return result;
	}
};

Middle 500 BaronsAndCoins

チェス盤上でバロンというコマを考える。バロンは$K_{i} < K_{i+1}$なる系列について、(x,y)から(x+K_{i},y+1)と動くことが出来る。盤面上で指定された複数のマーカーのうち、最大でいくつのマーカーを通過できるか求めよ。

DPなので捨てようかとも思いましたが、一応考えてみました。まず初めに考えたのは10000×10000のDPですが、計算量的に無理です。続いてマーカーの位置でDPが出来るかどうか考えてみました。O(50^4)くらい(?)で収まりそうな雰囲気だったので、これで書くことにしました。初めは状態をvector<vector<pair<int, int> > >で持っていたのですが、サブミット後の検証でTLEする場合があったため、vector<set<int, int> >でresubmitしました。結局撃墜されてしまったのですが、2箇所書き換えたら通りました。

以下は修正後のソースです。

class BaronsAndCoins {
public:
	int f(int x0, int y0, int k, int x1, int y1)
	{
		if (y0 >= y1) {
			return -1;
		}

		const int dx = x1 - x0;
		const int dy = y1 - y0;

		const int minDx = ((dy + k) * (dy + k + 1) - k * (k + 1)) / 2;
		if (dx < minDx) {
			return -1;
		}

		const int dk = (dx - minDx + dy - 1) / dy;

		return dk + k + dy; 
	}
	int getMaximum(vector <int> x, vector <int> y) {
		vector<pair<int, int> > targets;
		targets.push_back(make_pair(0, 0));
		for (int i = 0; i < x.size(); ++i) {
			targets.push_back(make_pair(x[i], y[i]));
		}

		sort(targets.begin(), targets.end());
		const int n = targets.size();

		//(取ったコマの数、K)
		vector<set<pair<int, int> > > nodes(n);
		nodes[0].insert(make_pair(0, 0));

		int result = 0;

		for (int from = 0; from < n; ++from) {
			const int x0 = targets[from].first;
			const int y0 = targets[from].second;
			for (set<pair<int, int> >::iterator it = nodes[from].begin(); it != nodes[from].end(); ++it) {
				const int k = it->second;
				for (int to = from + 1; to < n; ++to) {
					const int x1 = targets[to].first;
					const int y1 = targets[to].second;

					const int kk = f(x0, y0, k, x1, y1);
					if (kk < 0) {
						continue;
					}

					nodes[to].insert(make_pair(it->first + 1, kk));
					result = max(result, it->first + 1);
				}
			}

			nodes[from].clear();
		}

		return result;
	}
}

Hard 1000 BrickPuzzle

最大22×22のボードが白と黒に塗られている。テトラミノを置いて黒いマスを隠していくとき、全て隠すために必要なテトラミノの数を求めよ。

分かりません。

撃墜フェイズ

撃墜祭りのはずなのに手も足も出ませんでした・・・

システムテスト

o x x

総評

500が惜しかったです。もうちょっと注意していればいけたのかもしれません。

ゲスト



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