TopCoderOpen 2017 Regional Wildcard : Medium SixDegreesOfSeparation

なんだこりゃ。
https://community.topcoder.com/stat?c=problem_statement&pm=14688

問題

N頂点の連結無向グラフがある。
このグラフにN/3本以下の辺を追加し、任意の頂点間の距離を6以下にせよ。

解法

1つ頂点を定め、全頂点からその頂点までの距離が3以下になるようにすればよい。
適当に始点を定め、そこからDFSで頂点を辿ろう。
そして辿った頂点の視点からの距離をmod 3で分類する。
分類した3つのグループのどこかはN/3個以下の頂点数なので、それらと始点の間に辺がなければ追加すればよい。

vector<int> E[2020];
int mat[2020][2020];
vector<int> V[3];
int vis[2020];

class SixDegreesOfSeparation {
	public:
	void dfs(int cur,int depth) {
		if(vis[cur]) return;
		vis[cur]=1;
		if(cur!=0) V[depth%3].push_back(cur);
		FORR(e,E[cur]) dfs(e,depth+1);
	}
	
	vector <int> getAdditionalEdges(int n, vector <int> a, vector <int> b) {
		int i,x,y;
		ZERO(mat);
		ZERO(vis);
		FOR(i,n) E[i].clear();
		FOR(i,a.size()) E[a[i]].push_back(b[i]),E[b[i]].push_back(a[i]), mat[a[i]][b[i]]=mat[b[i]][a[i]]=1;
		FOR(i,3) V[i].clear();
		dfs(0,0);
		
		vector<int> ret;
		FOR(i,3) if(V[i].size()<=n/3) {
			FORR(e,V[i]) if(mat[0][e]==0) ret.push_back(0),ret.push_back(e);
			break;
		}
		return ret;
	}
}

まとめ

300-450-900とか変則的な配点は怖いね。