Hatena::Grouptopcoder

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

 | 

2013-12-24

Codeforces Round #221 (Div. 1) 01:24 Codeforces Round #221 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Round #221 (Div. 1) - nodchipのTopCoder日記 Codeforces Round #221 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

A. Divisible by Seven

  • next_permutationするだけかな・・・?
  • サンプルの2つ目でleading zeroが出てしまう
  • 先頭を1689にして、先頭4つだけnext_permutaionしたらいけるかな
  • 行けそう
  • Accepted
bool isDisibleBy7(const string& a) {
	int x = 0;
	for (const auto& ch : a) {
		x *= 10;
		x += ch - '0';
		x %= 7;
	}
	return x == 0;
}

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

	string a;
	cin >> a;
	int count[10];
	CLEAR(count);
	for (const auto& ch : a) {
		++count[ch - '0'];
	}

	string b = "1689";
	--count[1];
	--count[6];
	--count[8];
	--count[9];
	for (int i = 0; i < 10; ++i) {
		b += string(count[i], i + '0');
	}

	do {
		if (isDisibleBy7(b)) {
			cout << b << endl;
			return 0;
		}
	} while (next_permutation(b.begin(), b.begin() + 4));

	cout << 0 << endl;
}

B. Maximum Submatrix 2

  • "You are allowed to rearrange its rows."・・・
  • rearrangeなしバージョンのO(nm)は知っているけど・・・
  • どうするの全くわからない
  • ・・・
  • (一時間後)
  • 各セル毎に自分を含めて左側に1が何個続くか数えて、列毎にソートして矩形の面積調べていけばいいだけか
  • たしかにこれは思いつけば一発・・・orz
  • これすぐに思いつく人が羨ましい
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	static int matrix[8 * 1024][8 * 1024];
	int n, m;
	scanf("%d%d", &n, &m);
	//cin >> n >> m;
	for (int row = 0; row < n; ++row) {
		static char line[8192];
		scanf("%s", line);
		for (int column = 0; column < m; ++column) {
			matrix[row][column] = line[column] - '0';
			if (column > 0 && matrix[row][column] == 1) {
				matrix[row][column] += matrix[row][column - 1];
			}
		}
	}

	int answer = 0;
	for (int column = 0; column < m; ++column) {
		static int columns[8 * 1024];
		for (int row = 0; row < n; ++row) {
			columns[row] = matrix[row][column];
		}
		sort(columns, columns + n);

		for (int row = 0; row < n; ++row) {
			MAX_UPDATE(answer, columns[row] * (n - row));
		}
	}

	cout << answer << endl;
}

C. Circling Round Treasures

  • 探索でもするのだろうか・・・
  • O(2^8)が掛かるということ以外全く分からないorz

D. Tree and Queries

  • データ構造系は無理

E. Red and Black Tree

  • データ構造系は無理

Sstem Test

#Who= * A 500B 1000C 1500D 2000E 2500
179Japan nodchip1152 476 00:12676 01:21

B問題で、Javaを使った人、毎回配列をmemsetでクリアした人、配列のサイズを2のべき乗にしなかった人、vectorを使った人、cinを使った人などがTLEしたため、思ったより悪い順位ではありませんでした。

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