Hatena::Grouptopcoder

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

 | 

2010-07-01

Member Single Round Match 474 12:02 Member Single Round Match 474 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Member Single Round Match 474 - nodchipのTopCoder日記 Member Single Round Match 474 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 RouteIntersection

  • 次元でか!
  • sparseだから座標はmapで持たせることにする
  • 同じところに戻ってきたらNOT VALID出すだけか・・・

結果: Passed System Test

class RouteIntersection {
public:
	string isValid(int N, vector <int> coords, string moves) {
		set<map<int, int> > visited;
		map<int, int> pos;
		REP(i, coords.size()) {
			pos[coords[i]] = 0;
		}

		visited.insert(pos);

		REP(i, coords.size()) {
			const int index = coords[i];
			const int dir = moves[i] == '+' ? 1 : -1;
			pos[index] += dir;

			if (visited.count(pos)) {
				return "NOT VALID";
			}
			visited.insert(pos);
		}

		return "VALID";
	}
};

Middle 500 TreesCount

  • うげぇ・・・これDPだ・・・絶対DPだ・・・orz
  • とりあえず考えてみる
  • 頂点0からの最短路に関係ないところはけしちゃっておkだとおもう
  • 頂点数少ないから最短距離の計算はワーシャルフロイドでいいや
  • 消してみた
  • 残ったものは最短路に関係あるエッジ
  • ・・・
  • これ木を出すんだっけ・・・?
  • だったら0からの経路は1通りしかのいよなぁ
  • なら各頂点についてどこから辿れるかカウントして掛けてけばいいんじゃね?

結果: Passed System Test

static int g[64][64];

class TreesCount {
public:
	int count(vector <string> graph) {
		const int n = graph.size();
		REP(i, n) {
			REP(j, n) {
				g[i][j] = graph[i][j] - '0';
				if (i != j && g[i][j] == 0) {
					g[i][j] = INT_MAX / 2;
				}
			}
		}
		REP(k, n) {
			REP(i, n) {
				REP(j, n) {
					g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
				}
			}
		}

		REP(i, n) {
			REP(j, n) {
				if (graph[i][j] - '0' != abs(g[0][i] - g[0][j])) {
					graph[i][j] = '0';
				}
			}
		}

		// distance, nodeIndex
		vector<pair<int, int> > nodes;
		REP(i, n) {
			nodes.push_back(make_pair(g[0][i], i));
		}
		sort(ALL(nodes));

		ll result = 1;
		REP(i, n) {
			if (i == 0) {
				continue;
			}
			const int distance = nodes[i].first;
			const int to = nodes[i].second;

			int counter = 0;
			REP(from, n) {
				if (g[0][from] >= distance) {
					continue;
				}

				if (graph[from][to] - '0' == abs(g[0][from] - g[0][to])) {
					++counter;
				}
			}
			result *= counter;
			result %= 1000000007;
		}

		return result;
	}
}

Hard 1000 GameWithGraphAndTree

  • さっぱりわからない・・・orz

Challenge Phase

  • 500でintで計算して桁あふれしている人を探してみる
  • いた!
  • とおもったらlong longに変換してから計算してた
  • orz
  • 250も見てみる
  • 座標を配列で持っている人・・・
  • いるわけないかorz

System Test

o o x 509.52 2144->2132 まぁまぁだったと思います・・・。赤になりたい・・・。

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