Hatena::Grouptopcoder

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

 | 

2013-01-20

AtCoder Regular Contest #011 12:43 AtCoder Regular Contest #011 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest #011 - nodchipのTopCoder日記 AtCoder Regular Contest #011 - nodchipのTopCoder日記 のブックマークコメント

A - 鉛筆リサイクルの新技術

  • これUVAで8年くらいまえにやった気がする
  • 回すだけ
int main() {
	std::ios::sync_with_stdio(false);

	int m, n, N;
	cin >> m >> n >> N;

	int answer = N;
	int remain = N;
	while (remain >= m) {
		int set = remain / m;
		answer += set * n;
		remain -= set * m;
		remain += set * n;
	}
	cout << answer << endl;
}

B - ルイス・キャロルの記憶術

  • やるだけ
  • テーブル作るのが面倒くさい
const string FROM = "bctjlvpmngdwfqsxhkzr";
const string TO   = "11335577992244668800";

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

	map<char, char> dict;
	REP(i, FROM.size()) {
		dict[FROM[i]] = TO[i];
	}

	int N;
	cin >> N;
	bool first = true;
	REP(n, N) {
		string in;
		cin >> in;

		string out;
		REP(i, in.size()) {
			in[i] = tolower(in[i]);
			if (dict.count(in[i])) {
				out += dict[in[i]];
			}
		}

		if (out.empty()) {
			continue;
		}

		if (first) {
			first = false;
		} else {
			cout << " ";
		}

		cout << out;
	}
	
	cout << endl;
}

C - ダブレット

  • 幅優先してトラックバック
bool canGo(const string& a, const string& b) {
	if (a.size() != b.size()) {
		return false;
	}
	
	int count = 0;
	REP(i, a.size()) {
		if (a[i] != b[i]) {
			if (++count >= 2) {
				return false;
			}
		}
	}

	return true;
}

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

	vector<string> words;
	string start, goal;
	cin >> start >> goal;
	words.push_back(start);
	words.push_back(goal);

	int N;
	cin >> N;
	REP(n, N) {
		string word;
		cin >> word;
		words.push_back(word);
	}

	vector<vector<int> > graph(words.size());
	REP(from, words.size()) {
		REP(to, from) {
			if (!canGo(words[from], words[to])) {
				continue;
			}
			graph[from].push_back(to);
			graph[to].push_back(from);
		}
	}

	deque<int> q;
	q.push_back(1);
	vector<int> path(words.size(), -1);

	while (!q.empty()) {
		int current = q.front();
		q.pop_front();

		REP(i, graph[current].size()) {
			int next = graph[current][i];
			if (path[next] != -1) {
				continue;
			}

			path[next] = current;
			q.push_back(next);
		}
	}

	if (path[0] == -1) {
		cout << -1 << endl;
		return 0;
	}

	vector<int> answer;
	answer.push_back(0);
	while (answer.back() != 1) {
		answer.push_back(path[answer.back()]);
	}

	cout << answer.size() - 2 << endl;
	REP(i, answer.size()) {
		cout << words[answer[i]] << endl;
	}
}

D - きつねさんからの挑戦状

  • 乱択 -> 山登り法 とか・・・?
  • 1.9秒まで回してみる
  • TLE
  • ・・・?
  • 1.0秒だと回るなぁ
  • でもWA
  • 定数倍高速化
  • WA
  • ・・・
  • 解析的に解けるのかなぁ・・・
  • TLによると
    • 2つの住居の垂直二等分線
    • 2本の直線の角の二等分線
    • Rの境界
  • の交点を候補として全探索すればよかったそうです

System Test

順位ユーザ名鉛筆リサイクルの新技術ルイス・キャロルの記憶術ダブレットきつねさんからの挑戦状得点 / Total
5nodchip 100 04:29100 10:25100 24:07(8)300 24:07

Cが早めに解けたためとてもよい順位でした。D解きたかったです。

ゲスト



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