Hatena::Grouptopcoder

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

 | 

2011-01-22

Codeforces Beta Round #52 (Div. 2) 11:39 Codeforces Beta Round #52 (Div. 2) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #52 (Div. 2) - nodchipのTopCoder日記 Codeforces Beta Round #52 (Div. 2) - nodchipのTopCoder日記 のブックマークコメント

  • no ratedで参加

A. Bar

  • istringstreamの>>演算子は正しく読み取れた場合はtrue相当、読み取れなかった場合はfalse相当の値を返すらしので、これを利用して数字かどうかを判定する
  • Accepted
static const string alcholsList[] = {"ABSINTH", "BEER", "BRANDY", "CHAMPAGNE", "GIN", "RUM", "SAKE", "TEQUILA", "VODKA", "WHISKEY", "WINE"};

int main() {
	set<string> alchols(alcholsList, alcholsList + sizeof(alcholsList) / sizeof(alcholsList[0]));
	int N;
	cin >> N;
	int answer = 0;
	REP(n, N) {
		string word;
		cin >> word;
		int age;
		if (istringstream(word) >> age) {
			if (age < 18) {
				++answer;
			}
		} else {
			if (alchols.count(word)) {
				++answer;
			}
		}
	}
	cout << answer << endl;
}

B. Spoilt Permutation

  • 数字が順番通りに並んでいない箇所をreverseして、元の配列と一致したかどうかを判定する
  • Accepted
int main() {
	int N;
	cin >> N;
	vector<int> coins;
	vector<int> permutations;
	REP(n, N) {
		int coin;
		cin >> coin;
		coins.push_back(coin);
		permutations.push_back(n + 1);
	}

	int begin = 0;
	for (; begin < N; ++begin) {
		if (coins[begin] != permutations[begin]) {
			break;
		}
	}

	int end = N - 1;
	for (; end >= 0; --end) {
		if (coins[end] != permutations[end]) {
			break;
		}
	}

	if (begin > end) {
		cout << "0 0" << endl;
		return 0;
	}

	reverse(permutations.begin() + begin, permutations.begin() + end + 1);

	if (coins == permutations) {
		cout << begin + 1 << " " << end + 1 << endl;
	} else {
		cout << "0 0" << endl;
	}
}

C. Corporation Mail

  • 英語が読めない
  • しょうがないからSample Input見て勘で答える!
  • 木が与えられて、あるノードとその子孫ノードの値が等しくなるようなペアが何通りあるか?
  • パーサーにそれまでに何回値が出たかを伝搬させて終わり
  • Accepted
char buffer[1024];
char* p;
map<string, int> m;
// # employee ::= name. | name:employee1,employee2, ... ,employeek. 
int dfs() {
	string name;
	while (isupper(*p)) {
		name += *p++;
	}
	int res = m[name];
	++m[name];
	while (*p != '.') {
		++p;
		res += dfs();
	}
	++p;
	--m[name];
	return res;
}

int main() {
	scanf("%s", buffer);
	p = buffer;
	cout << dfs() << endl;
}

D. Changing a String

  • 見た感じバックトラック付きの編集距離のDP
  • 書けた
  • Runtime error on test 8
  • なんですと!?
  • orz
  • バックトラック用の配列の初期化忘れてる・・・orz
  • 以下はPracticeで通したソースコードです
static int dp[1024][1024];
static int type[1024][1024];
static int go[1024][1024];
int main() {
	string a, b;
	getline(cin, a);
	getline(cin, b);

	const int A = a.length();
	const int B = b.length();

	for (int i = 0; i <= A; ++i) {
		dp[i][0] = i;
		type[i][0] = 0;
	}
	for (int j = 0; j <= B; ++j) {
		dp[0][j] = j;
		type[0][j] = 1;
	}

	for (int i = 1; i <= A; ++i) {
		for (int j = 1; j <= B; ++j) {
			const int cost = a[i - 1] == b[j - 1] ? 0 : 1;

			dp[i][j] = dp[i - 1][j] + 1;
			type[i][j] = 0;

			if (dp[i][j] > dp[i][j - 1] + 1) {
				dp[i][j] = dp[i][j - 1] + 1;
				type[i][j] = 1;
			}

			if (dp[i][j] > dp[i - 1][j - 1] + cost) {
				dp[i][j] = dp[i - 1][j - 1] + cost;
				type[i][j] = 2;
			}
		}
	}

	vector<string> command;

	int r = A;
	int c = B;
	while (r || c) {
		if (type[r][c] == 0) {
			--r;
			go[r][c] = 0;

		} else if (type[r][c] == 1) {
			--c;
			go[r][c] = 1;

		} else if (type[r][c] == 2) {
			--r;
			--c;
			go[r][c] = 2;

		} else {
			assert(false);
		}
	}

	r = 0;
	c = 0;
	while (r != A || c != B) {
		if (go[r][c] == 0) {
			char buffer[1024];
			sprintf(buffer, "DELETE %d", c + 1);
			command.push_back(buffer);
			++r;

		} else if (go[r][c] == 1) {
			char buffer[1024];
			sprintf(buffer, "INSERT %d %c", c + 1, b[c]);
			command.push_back(buffer);
			++c;

		} else if (go[r][c] == 2) {
			if (a[r] != b[c]) {
				char buffer[1024];
				sprintf(buffer, "REPLACE %d %c", c + 1, b[c]);
				command.push_back(buffer);
			}
			++r;
			++c;

		} else {
			assert(false);
		}
	}

	cout << command.size() << endl;
	REP(i, command.size()) {
		cout << command[i] << endl;
	}
}

E. Domino Principle

  • 普通にやるとO(N^2)でTLE
  • TLEしないようにするためには、配列のある範囲の最大値をO(logN)位で取得しなければならない気がする
  • そんなのできたっけ・・・?
    • ここでタイムアップ
  • TL見ていたら平方分割とか書かれている
  • 言われてみれば平方分割だとかそのあたりのどれかで行ける気がする
  • ということでiwiwi先生のスライドをもとにセグメント木で実装してみた
  • そのまま答えを入れるとダメで、インデックス分引いいておかないといけない
  • 以下はPracticeで通したソースコードです
class SegmentTree {
public:
	// sizeは2のべき乗
	void init(int size) {
		data.clear();
		data.resize(size * 2 - 1, INT_MIN);
		indexes.clear();
		indexes.resize(size * 2 - 1, INT_MIN);
		REP(i, size) {
			indexes[i + size - 1] = i;
		}
	}

	// i番目をxに変更する
	void update(int i, int size, int x) {
		i += size - 1;
		data[i] = x;
		while (i) {
			i = (i - 1) / 2;
			if (data[i * 2 + 1] < data[i * 2 + 2]) {
				data[i] = data[i * 2 + 2];
				indexes[i] = indexes[i * 2 + 2];
			} else {
				data[i] = data[i * 2 + 1];
				indexes[i] = indexes[i * 2 + 1];
			}
		}
	}

	// [a, b)の最大値
	// 外からはquery(a, b, 0, 0, size)のように呼ぶ
	pair<int, int> query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return MP(INT_MIN, INT_MIN);
		}
		if (a <= l && r <= b) {
			return MP(data[k], indexes[k]);
		}
		const pair<int, int> vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		const pair<int, int> vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		if (vl.first < vr.first) {
			return vr;
		} else {
			return vl;
		}
	}

private:
	vector<int> data;
	vector<int> indexes;
};

struct Domino {
	int x, h, index, answer;
	Domino() { }
	Domino(int x) : x(x) { }
	static bool compareByX(const Domino& lh, const Domino& rh) {
		return lh.x < rh.x;
	}
	static bool compareByIndex(const Domino& lh, const Domino& rh) {
		return lh.index < rh.index;
	}
};

SegmentTree st;

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

	vector<Domino> dominos;
	REP(n, N) {
		Domino d;
		cin >> d.x >> d.h;
		d.index = n;
		dominos.push_back(d);
	}

	sort(ALL(dominos), Domino::compareByX);
	
	static const int SIZE = 1 << 17;
	SegmentTree st;
	st.init(SIZE);

	for (int currentIndex = N - 1; currentIndex >= 0; --currentIndex) {
		Domino& current = dominos[currentIndex];
		const int end = distance(dominos.begin(), lower_bound(dominos.begin() + currentIndex, dominos.end(), Domino(current.x + current.h), Domino::compareByX));
		pair<int, int> p = st.query(currentIndex, end, 0, 0, SIZE);
		const int answer = max(1, p.first + p.second - currentIndex + (N - 1 - p.second));
		st.update(currentIndex, SIZE, answer - (N - 1 - currentIndex));
		current.answer = answer;
	}

	sort(ALL(dominos), Domino::compareByIndex);

	REP(i, dominos.size()) {
		cout << dominos[i].answer << " ";
	}
	cout << endl;
}

Hack

  • Bで境界条件とTLEを狙う
  • 変数未初期化見つけた!
  • Unsuccessful hacking attempt
  • あれ?
  • ああ、大域変数だから0で初期化されているのかorz
  • お、TLEしそうなの発見!
  • Successful hacking attempt
  • もう一個発見!
  • Unsuccessful hacking attempt
  • あれ?
  • 今度は本気で訳がわからないorz

System Test

#Who=ABCDE
40 nodchip2760+1 / -2490 00:05944 00:141326 00:29-3

あんまり満足できない結果となりました。Dは解きたかったですorz

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