Hatena::Grouptopcoder

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

 | 

2010-04-16

Codeforces Beta Round #8 21:33 Codeforces Beta Round #8 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #8 - nodchipのTopCoder日記 Codeforces Beta Round #8 - nodchipのTopCoder日記 のブックマークコメント

Problem A Train and Peter

  • やるだけ
int main() {
	string colors, a, b;
	cin >> colors >> a >> b;
	bool forward = false;
	size_t index;
	if ((index = colors.find(a)) != string::npos) {
		forward = colors.find(b, index + a.size()) != string::npos;
	}

	reverse(colors.begin(), colors.end());
	bool backward = false;
	if ((index = colors.find(a)) != string::npos) {
		backward = colors.find(b, index + a.size()) != string::npos;
	}

	if (forward && backward) {
		cout << "both" << endl;
	} else if (forward) {
		cout << "forward" << endl;
	} else if (backward) {
		cout << "backward" << endl;
	} else {
		cout << "fantasy" << endl;
	}
}

Problem B Obsession with Robots

  • 一度訪れたマス、またはその上下左右のマスに来た場合は直接そのマスに行くルートがあるので最適ではない
  • 訪れたマスをメモするだけ
static const int DX[] = {1, -1, 0, 0};
static const int DY[] = {0, 0, 1, -1};

bool check(const string& in) {
	int dx[128];
	int dy[128];
	memset(dx, 0, sizeof(dx));
	memset(dy, 0, sizeof(dy));
	dx['R'] = 1;
	dx['L'] = -1;
	dy['U'] = 1;
	dy['D'] = -1;

	set<pair<int, int> > memo;
	memo.insert(make_pair(0, 0));

	int x = 0;
	int y = 0;
	for (string::const_iterator it = in.begin(); it != in.end(); ++it) {
		const char c = *it;
		const int nextX = x + dx[c];
		const int nextY = y + dy[c];
		
		if (memo.count(make_pair(nextX, nextY))) {
			return false;
		}

		int counter = 0;
		for (int direction = 0; direction < 4; ++direction) {
			if (memo.count(make_pair(nextX + DX[direction], nextY + DY[direction]))) {
				++counter;
			}
		}
		
		if (counter >= 2) {
			return false;
		}

		x = nextX;
		y = nextY;
		memo.insert(make_pair(x, y));
	}

	return true;
}

int main() {
	string in;
	cin >> in;

	if (check(in)) {
		cout << "OK" << endl;
	} else {
		cout << "BUG" << endl;
	}
}

Problem C Looking for Order

  • 巡回セールスマンで解けるだろうと誤解しO(2^N N^2)突っ込んでTLE
  • 幅優先っぽく書き換えるもPE
  • PEってどういうこと・・・

Problem D Two Friends

  • 考えていません

Problem E Beads

  • 考えていません
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100416
 |