Hatena::Grouptopcoder

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

 | 

2013-01-21

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

A. Escape from Stones

  • サンプルを見た感じではlとrで別の配列に入れていって、最後にくっつければ良い感じ
  • CodeForcesのAとしては良心的
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	string s;
	cin >> s;
	vector<int> left;
	vector<int> right;

	REP(i, s.size()) {
		char ch = s[i];
		if (ch == 'r') {
			left.push_back(i + 1);
		} else {
			right.push_back(i + 1);
		}
	}

	REP(i, left.size()) {
		cout << left[i] << endl;
	}
	for (vector<int>::reverse_iterator rit = right.rbegin(), ritEnd = right.rend(); rit != ritEnd; ++rit) {
		cout << *rit << endl;
	}
}

B. Good Sequences

  • ぱっと思いつくのはO(n^2)DP
  • もちろんTLE
  • さてどうしよう・・・
  • lengthの長い方から調べればすぐにヒットするかなぁ
  • 書いてみる
  • n=100000でTLEする
  • 素数の場合が遅いのだから、そこだけ別扱いしたらどうだろう
  • 一瞬で終わった
  • Accepted
vector<int> lengthToValue[128 * 1024];

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

int findLength(int bestLength, int value) {
	for (int length = bestLength; length >= 1; --length) {
		REP(i, lengthToValue[length].size()) {
			int p = lengthToValue[length][i];
			if (gcd(p, value) > 1) {
				return length;
			}
		}
	}
	return 0;
}
// エラトステネスの篩
#define MAX (256*1024)

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

	static bool flag[MAX];
	memset(flag, -1, sizeof(flag));
	flag[0] = flag[1] = false;
	for (int i = 2; i * i < MAX; ++i){
		if (!flag[i]){
			continue;
		}
		for (int j = i * i; j < MAX; j += i){
			flag[j] = false;
		}
	}

	int n;
	cin >> n;
	int answer = 0;

	REP(i, n) {
		int a;
		cin >> a;
		int length;
		if (flag[a]) {
			length = 1;
		} else {
			length = findLength(answer, a) + 1;
		}
		MAX_UPDATE(answer, length);
		lengthToValue[length].push_back(a);
	}

	cout << answer << endl;
}

C. Choosing Balls

  • 全くわからない
  • O(n q log(n))なら分かるけど多分TLE
  • とりあえず書き始めてみる
  • ・・・
  • 書き終わらない・・・
  • DP苦手orz

D. Colorful Stones

  • 全くわからないorz

Hack

  • Bで素数を別処理していない人を探す
  • いた
  • n=100000を投入
  • 成功
  • その他怪しい人を写景して狙ってみる
  • 無理っぽい

System Test

#Who=A 500B 1000C 1500D 2000E 2500
231nodchip1500+1492 00:04908 00:23

致命傷にならずに済みました

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