久々に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解けたかも。