Hatena::Grouptopcoder

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

 | 

2014-04-12

AtCoder Regular Contest 021 22:44 AtCoder Regular Contest 021 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest 021 - nodchipのTopCoder日記 AtCoder Regular Contest 021 - nodchipのTopCoder日記 のブックマークコメント

A - DEAD END

  • 2048ですね・・・
  • AI書きました・・・
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int b[4][4];
	REP(r, 4) REP(c, 4) {
		cin >> b[r][c];
	}

	bool gameover = true;
	REP(r, 4) REP(c, 4) {
		if (r + 1 < 4 && b[r][c] == b[r + 1][c]) {
			gameover = false;
		}
		if (c + 1 < 4 && b[r][c] == b[r][c + 1]) {
			gameover = false;
		}
	}

	cout << (gameover ? "GAMEOVER" : "CONTINUE") << endl;
}

B - Your Numbers are XORed...

  • 先頭の数字が決まれば残りの数字は一意に決まる
  • 先頭の数字が最小になるような解を見つければ辞書順になる
  • 先頭の数字はビットごとに独立して計算できる
  • 先頭の数字を貪欲に決めれば良いっぽい
bool check(const vector<int>& Bs, int shift, int A0) {
	int a = A0;
	REP(i, Bs.size()) {
		a ^= (Bs[i] >> shift) & 1;
	}
	return a == A0;
}

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

	int L;
	cin >> L;
	vector<int> Bs;
	REP(l, L) {
		int b;
		cin >> b;
		Bs.push_back(b);
	}

	int answer = 0;
	for (int shift = 0; shift <= 30; ++shift) {
		if (check(Bs, shift, 0)) {
			continue;
		}
		else if (check(Bs, shift, 1)) {
			answer |= 1 << shift;
			continue;
		}

		cout << -1 << endl;
		return 0;
	}

	REP(l, L) {
		cout << answer << endl;
		answer ^= Bs[l];
	}
}

C - 増築王高橋君

  • 最後に買う建物の金額で二分探索
  • 価格が決まれば各建物ごとに増築した回数が決まる
  • ・・・
  • って通らない・・・
  • うむむ
  • とりあえず遅いバージョンを投げてみる
  • WA 55
  • 分からんorz
// price以下の建物を全部買ってK以上ならtrue
bool check(ll price) {
	ll k = 0;
	REP(n, N) {
		if (price < A[n]) {
			continue;
		}
		k += (price - A[n]) / D[n] + 1;
	}
	return K <= k;
}
 
int main() {
	std::ios::sync_with_stdio(false);
 
	cin >> K >> N;
	REP(n, N) {
		cin >> A[n] >> D[n];
	}
 
	multimap<ll, pair<int, ll> > q;
	ll spentMoney = 0;
	ll numberOfExtensions = 0;
	REP(i, N) {
		q.insert(MP(A[i], MP(i, 0)));
	}
 
	assert(numberOfExtensions <= K);
 
	while (numberOfExtensions < K) {
		ll price = q.begin()->first;
		int itemIndex = q.begin()->second.first;
		ll extensions = q.begin()->second.second;
 
		q.erase(q.begin());
 
		spentMoney += price;
		price += D[itemIndex];
		++extensions;
 
		q.insert(MP(price, MP(itemIndex, extensions)));
 
		++numberOfExtensions;
	}
 
	cout << spentMoney << endl;
}

D - だいたい最小全域木

  • 考えていません

結果

順位ユーザ名DEAD ENDYour Numbers are XORed...増築王高橋君だいたい最小全域木得点 / Total
54nodchip100 02:26100 15:2055 (3) 77:38-255 (3) 92:38
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140412
 |