Hatena::Grouptopcoder

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

 | 

2010-05-30

CodeForces Beta Round #15 16:30 CodeForces Beta Round #15  - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - CodeForces Beta Round #15  - nodchipのTopCoder日記 CodeForces Beta Round #15  - nodchipのTopCoder日記 のブックマークコメント

A. Cottage Village

  • 最近座標の2倍化がブームなので2倍化してみた
  • 中心の位置でソート
  • 隣り合う部分に家を立てられるかどうかチェック
int main() {
	int n, t;
	cin >> n >> t;
	t *= 2;
	vector<pair<int, int> > houses;
	
	REP(i, n) {
		int x, a;
		cin >> x >> a;
		x *= 2;
		houses.push_back(make_pair(x, a));
	}

	sort(ALL(houses));

	int answer = 2;
	REP(i, houses.size() - 1) {
		int d = houses[i + 1].first - houses[i + 1].second - houses[i].first - houses[i].second;
		if (d == t) {
			++answer;
		} else if (d > t) {
			answer += 2;
		}
	}

	cout << answer << endl;
}

B. Laser

  • 直接計算するのは面倒な気がした
  • それぞれのレーザーが当てられる部分と
  • 両方のレーザーが当てられる部分を計算して
  • 元の面積から足したり引いたり
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		ll n, m, x1, y1, x2, y2;
		cin >> n >> m >> x1 >> y1 >> x2 >> y2;
		if (x1 > x2) {
			swap(x1, x2);
		}
		if (y1 > y2) {
			swap(y1, y2);
		}

		const ll dx = x2 - x1;
		const ll dy = y2 - y1;
		const ll w = n - dx;
		const ll h = m - dy;
		const ll ww = max(0LL, n - 2 * dx);
		const ll hh = max(0LL, m - 2 * dy);

		const ll answer = n * m - w * h * 2 + ww * hh;
		cout << answer << endl;
	}
}

C. Industrial Nim

  • ゲーム木きたー!
  • オワタorz
  • と言うわけにも行かないので取り敢えず解いてみる
  • 適当に書いて送ってみた
  • WA
  • こういう時はWikipedia先生にお伺いを立て見る
  • 全部xorして0で無ければ勝ちなのだそうだ
    • そう言えばそんな話を昔聞いたような・・・
  • つまり0~でっかい数までのxorを求める問題に帰着するわけだ
  • カリカリ書いてみた
ll sumXor(ll n) {
	ll first = n % 4;
	ll answer = (first == 1 || first == 2) ? 1 : 0;
	ll two = 2;
	for (int bit = 1; bit < 63; ++bit) {
		ll b;
		ll i = n % (two * 2);
		if (i < two) {
			b = 0;
		} else {
			b = 1 - (n & 1);
		}
		answer |= (b << bit);

		two *= 2;
	}
	return answer;
}

int main() {
	int n;
	cin >> n;

	ll flag = 0;
	for (int i = 0; i < n; ++i) {
		ll m, x;
		cin >> x >> m;
		flag ^= sumXor(x - 1);
		flag ^= sumXor(x + m - 1);
	}

	if (flag) {
		cout << "tolik" << endl;
	} else {
		cout << "bolik" << endl;
	}
}

D. Map

  • Cで時間を食い過ぎて時間がなくなったのでパス

E. Triangles

  • 同様にパス
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100530
 |