Hatena::Grouptopcoder

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

 | 

2012-02-25

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

A - Hometask

  • これはabaという形とabという形を先頭から舐めるだけでいいのかなぁ
  • それだとabbbbaという形に対応できなさそう
  • ならどうすればよいか・・・
  • 同じペアに所属している文字が連続しているところで分割して、文字数の少ない方を引き抜けば良いのか
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	string S;
	int K;
	cin >> S >> K;
	map<char, int> forbiddens;
	for (char ch = 'a'; ch <= 'z'; ++ch) {
		forbiddens[ch] = ch;
	}
	REP(k, K) {
		char a, b;
		cin >> a >> b;
		forbiddens[a] = k;
		forbiddens[b] = k;
	}

	int answer = 0;
	int lastType = -1;
	map<char, int> count;
	REP(i, S.size()) {
		char ch = S[i];
		int type = forbiddens[ch];
		if (type != lastType) {
			if (count.size() == 2) {
				int minValue = INT_MAX;
				for (map<char, int>::iterator it = count.begin(), itEnd = count.end(); it != itEnd; ++it) {
					MIN_UPDATE(minValue, it->second);
				}
				answer += minValue;
			}
			count.clear();
		}
		++count[ch];
		lastType = type;
	}

	if (count.size() == 2) {
		int minValue = INT_MAX;
		for (map<char, int>::iterator it = count.begin(), itEnd = count.end(); it != itEnd; ++it) {
			MIN_UPDATE(minValue, it->second);
		}
		answer += minValue;
	}

	cout << answer << endl;
}

B - Colliders

  • ある加速器をオンにする時に、他のオンになっている加速器を全て調べたらTLE
  • 多分使用している約数を覚えておいて、同じ約数を使っている加速器があるかどうかを調べれば良いのかな?
  • コーナーケースは"1"の時
  • これはどうなるんだろう・・・
  • "two numbers are relatively prime if their greatest common divisor equals 1"って書いてあるから"1"は他の加速器と同時に動かしてはならないに違いない (<-間違い!!!)
  • まずは素因数分解っぽいコードを書いて
  • 次に1の場合に注意しながらコードを書く
  • Submit
  • ・・・?
  • 素因数分解間違ってた!!!
  • Submit
  • ・・・?
  • 問題文をよく読みなおしてみる
  • ・・・
  • "two numbers are relatively prime if their greatest common divisor equals 1"って"1"は他の加速器と同時に動かして良いってこと・・・?
  • 書きなおしてみる
  • Submit
    • Accepted
  • この問題解釈間違いはひどすぎるorz
vector<int> memo[128 * 1024];
const vector<int>& factrize(int N) {
	vector<int>& s = memo[N];
	if (s.empty()) {
		int n = N;
		set<int> ss;
		for (int i = 2; i * i <= n; ++i) {
			while (n % i == 0) {
				ss.insert(i);
				n /= i;
			}
		}
		if (n != 1) {
			ss.insert(n);
		}
		s.insert(s.end(), ALL(ss));
	}
	return s;
}

void test() {
	vector<int> a;
	a.clear();
	a.push_back(2);
	a.push_back(3);
	assert(a == factrize(48));

	a.clear();
	a.push_back(2);
	a.push_back(3);
	assert(a == factrize(36));

	a.clear();
	a.push_back(13);
	assert(a == factrize(13));

	a.clear();
	a.push_back(2);
	a.push_back(5);
	assert(a == factrize(100000));
}

set<int> alreadys[128 * 1024];
int main() {
	test();

	std::ios::sync_with_stdio(false);

	// 1の特別処理
	int N, M;
	cin >> N >> M;

	set<int> already;
	REP(m, M) {
		char ch;
		int i;
		cin >> ch >> i;

		const vector<int>& factors = factrize(i);
		//if (i == 1) {
		//	if (ch == '+') {
		//		if (already.count(1)) {
		//			//printf("1\n");
		//			assert(already.size() == 1);
		//			printf("Already on\n");
		//		} else if (!already.empty()) {
		//			//printf("2\n");
		//			printf("Conflict with %d\n", *already.begin());
		//		} else {
		//			//printf("3\n");
		//			printf("Success\n");
		//			already.insert(1);
		//		}
		//	} else {
		//		if (already.count(1)) {
		//			assert(already.size() == 1);
		//			//printf("4\n");
		//			printf("Success\n");
		//			already.erase(1);
		//		} else {
		//			//printf("5\n");
		//			printf("Already off\n");
		//		}
		//	}
		//} else {
			if (ch == '+') {
				if (already.count(i)) {
					//printf("5\n");
					printf("Already on\n");
				//} else if (already.count(1)) {
				//	//printf("10\n");
				//	printf("Conflict with %d\n", 1);
				} else {
					int found = -1;
					for (vector<int>::const_iterator it = factors.begin(), itEnd = factors.end(); it != itEnd; ++it) {
						if (!alreadys[*it].empty()) {
							found = *alreadys[*it].begin();
						}
					}

					if (found == -1) {
						//printf("6\n");
						printf("Success\n");
						for (vector<int>::const_iterator it = factors.begin(), itEnd = factors.end(); it != itEnd; ++it) {
							alreadys[*it].insert(i);
						}
						already.insert(i);
					} else {
						//printf("7\n");
						printf("Conflict with %d\n", found);
					}
				}
			} else {
				if (already.count(i)) {
					//printf("8\n");
					printf("Success\n");
					for (vector<int>::const_iterator it = factors.begin(), itEnd = factors.end(); it != itEnd; ++it) {
						alreadys[*it].erase(i);
					}
					already.erase(i);
				} else {
					//printf("9\n");
					printf("Already off\n");
				}
			}
		//}
	}
}

C - Double Profiles

  • 全くわかりませんでした

D - Flatland Fencing

  • 読んでいません

E - Martian Colony

  • 読んでいません

Hack

  • しませんでした

System Test

#Who= ABCDE
251nodchip1036 460 00:20576 01:21-7

1838 -> 1837 他の方がBで頓死したせいか現状維持ですみました・・・。

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