MemberSRM470 Div1 500 DrawingLines

本番で解けなかった問題シリーズ．

問題

• 長方形の上辺と下辺にそれぞれn(≦10000)個の点が打ってある
• 上辺の点と下辺の点すべてを1対1でランダムで結ぶ
  • 高々50個のペアは既に線が結んである
• 交差する線分のペアの数の期待値は？

解法

• 上辺の2点について，そこから引いた2本の線分が交差する確率を足す
  • 選んだ2点の両方から既に線が引いてあるとき
    • その線分が交わってれば確率1，交わってなければ確率0
  • 片方からすでに線が引いてあるとき
    • もう片方から，交わるように点を選ぶ確率を求める
  • 両方の点についてまだ線が引かれていないとき
    • 下辺の2点を選ぶと交差させるか，させないかの2通りなので確率0.5
• 頑張ればもうちょっと簡単な式で計算できるんだろうな・・・。

#include <iostream>
#include <vector>

using namespace std;

class DrawingLines{
public:
    double countLineCrossings(int n, vector<int> startDot, vector<int> endDot){
        int con[10000];
        memset(con, -1, sizeof(con));
        int ns = startDot.size();
        for(int i=0;i<ns;i++) con[startDot[i]-1] = endDot[i]-1;
        double res = 0.0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(con[i]!=-1&&con[j]!=-1) res += (con[j]<con[i]);
                else if(con[i]!=-1||con[j]!=-1){
                    if(con[i]!=-1){
                        int cnt = con[i];
                        for(int k=0;k<ns;k++) cnt -= (endDot[k]-1 < con[i]);
                        res += (double)cnt/(n-ns);
                    } else {
                        int cnt = n-con[j]-1;
                        for(int k=0;k<ns;k++) cnt -= (endDot[k]-1 > con[j]);
                        res += (double)cnt/(n-ns);
                    }
                }
                else res += 0.5;
            }
        }
        return res;
    }
};