kmjp's blog

競技プログラミング参加記です

TopCoder SRM 746 Div1 Easy ChangeDistances

しょうもないミスでレート100落ちるのしんどいですね。
https://community.topcoder.com/stat?c=problem_statement&pm=15272

問題

無向グラフGが与えられる。
同じ頂点数のグラフHのうち、2点間(u,v)の最短距離がいずれもGと異なるものを答えよ。

解法

直結している頂点対の距離は1確定で、そうでないものは連結しているかしていないかわからないがとにかく1以外である。
よって、Gにおける辺の有無を反転させれば、距離も1か1でないものの間で入れ替わるので条件を満たす。

class ChangeDistances {
	public:
	vector <string> findGraph(vector <string> g) {
		vector<string> h=g;
		int N=g.size();
		int y,x;
		FOR(y,N) FOR(x,N) if(y!=x) h[y][x]^=1;
		return h;
		
	}
}

まとめ

まぁこれは本番も瞬殺だったしね。