SRM470 div1 medium
解けなっかた人が解説しても仕方がないのでぐぐればいいと思うよ。
全探索。
#include <vector> using namespace std; class DrawingLines { public: double countLineCrossings(int n, vector <int> startDot, vector <int> endDot) { vector<int> ceil(n,-1); int m=startDot.size(); for(int i=0;i<m;i++) ceil[startDot[i]-1]=endDot[i]-1; double ans=0.0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(ceil[i]==-1 && ceil[j]==-1) ans+=0.5; else if(ceil[i]==-1 && ceil[j]!=-1) { int c=n-ceil[j]-1; for(int k=0;k<m;k++) if(ceil[j]<endDot[k]-1) c--; ans+=double(c)/double(n-m); } else if(ceil[i]!=-1 && ceil[j]==-1) { int c=ceil[i]; for(int k=0;k<m;k++) if(endDot[k]-1<ceil[i]) c--; ans+=double(c)/double(n-m); } else ans+=(ceil[j]<ceil[i])?1:0; return ans; } };