kmjp's blog

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

TopCoder SRM 801: Div1 Easy Div2 Hard SecondDiameters

久々にMedium通らない地獄を抜けた。
https://community.topcoder.com/stat?c=problem_statement&pm=16825&rd=18530

問題

2次元座標中の点集合における、二番目の直径とは、以下を指す。

  • 全頂点対の距離の(multisetではなく)集合のうち2番目に大きな値

今N個の頂点が与えられる。
1個頂点を取り除いた場合の残りの(N-1)頂点の二番目の直径について、各点を取り除いた場合における二乗和を求めよ。

解法

時間を気にしなければ、mapで距離と頻度の対応を覚えておき、1頂点vを取り除く場合、vと他の頂点の距離の分を先ほどのmapから引いたうえで、mapを距離の大きい順に探索すればよい。
ただ、O(N^2)通りの値をmapで参照・更新するとTLEする。
そこで、距離と頻度の対応はvector+sortで作るようにしよう。

map<int,int> M;
unordered_map<int,int> M2;

class SecondDiameters {
	public:
	long long getSecondDiameters(vector <int> X, vector <int> Y) {
		int N=X.size();
		int x,y;
		M.clear();
		vector<int> V;
		FOR(x,N) FOR(y,N) {
			V.push_back(-((X[x]-X[y])*(X[x]-X[y])+(Y[x]-Y[y])*(Y[x]-Y[y])));
		}
		sort(ALL(V));
		vector<pair<int,int>> W;
		FORR(v,V) {
			if(W.empty()||W.back().first!=-v) W.push_back({-v,0});
			W.back().second++;
		}
		
		ll ret=0;
		FOR(x,N) {
			M2.clear();
			FOR(y,N) M2[((X[x]-X[y])*(X[x]-X[y])+(Y[x]-Y[y])*(Y[x]-Y[y]))]+=2;
			ll tmp=-1;
			FORR(m,W) {
				if(m.second>M2[m.first]) {
					if(tmp==-1) tmp=-2;
					else {
						tmp=m.first;
						break;
					}
				}
			}
			ret+=tmp;
		}
		return ret;
		
	}
}

まとめ

最初mapだけで書いたら最大ケースで4sぐらいかかったため、vector+sortで書き直した。
お蔭で8Chal400pt稼げたので、書き直したかいがあった…と思ったけど、その時間でHard解けたかも。