Codeforces #315 Div1 D. Sign Posts

うーん、乱択の回数を微調整して無理やり通してるのでちょっとよくない解法。
http://codeforces.com/contest/568/problem/D

問題

２次元座標平面中にN個の直線がある。
この平面中に最大K個の点を置き、各直線が少なくとも１個の点を通過するようにしたい。

条件を満たす点の置き方が存在すれば、それを求めよ。

解法

この問題はNが最大10^5と大きくKが最大5と小さい。
１個点を置くにはできるだけ多くの直線が通る場所に置いた方が良い。

以下乱択でそのような候補を求める。
状態として[残った直線一覧][置ける点の数]として1個ずつDFSで置き方を考える。

まず残った直線(まだ点を通過していない直線)の数が点の数以下なら、各直線毎に１個ずつ点を置けばいいのでそれで終了。
問題は残った直線の数が点の数より多い場合である。
この場合、点を置くならば(残った直線数)/(置ける点の数)程度の直線が通過する場所に置きたい。

よって、まず直線を１つ乱択で選ぶ。
そしてその直線と他の直線との交点を求める。
最も多くの直線が通過する交点があり、かつ通過する直線数が(残った直線数)/(置ける点の数)以上であるなら、そこを点の候補とし、DFSで次の点を探索する。

以下の回答では、60回そんな乱択による選択を行っている。
乱択回数をちょっと減らすとWAになるし、ちょっと増やすとTLEするので注意。

int N,K;
ll A[101010],B[101010],C[101010];
vector<pair<int,int> > P;
mt19937 rsrc;

// a1x+b1y=c1, a2x+b2y=c2
pair<double,double> cross(ll a1,ll b1,ll c1,ll a2,ll b2,ll c2) {
	if(a1*b2==a2*b1) return make_pair(1e100,1e100);
	double d=a1*b2-a2*b1;
	double x = b2*c1-b1*c2;
	double y = -a2*c1+a1*c2;
	return make_pair(x/d,y/d);
}

void dfs(vector<int> V,int L) {
	if(V.size()<=L) {
		FORR(r,V) P.push_back({r,-1});
		_P("YES\n%d\n",P.size());
		FORR(r,P) _P("%d %d\n",r.first,r.second);
		exit(0);
	}
	if(L==0) return;
	
	int i, id=rsrc()%V.size(),x;
	vector<pair<double,double> > CP(V.size()),CP2;
	CP2.reserve(V.size());
	FOR(i,V.size()) {
		CP[i]=cross(A[V[i]],B[V[i]],-C[V[i]],A[V[id]],B[V[id]],-C[V[id]]);
		if(CP[i].first!=1e100) CP2.push_back(CP[i]);
	}
	
	if(CP2.empty()) return;
	sort(CP2.begin(),CP2.end());
	int ma=0,cur=0;
	pair<double,double> cand,pre({1e100,1e100});
	FORR(r,CP2) {
		if(pre!=r) cur=0,pre=r;
		cur++;
		if(cur>ma) ma=cur,cand=r;
	}
	
	if(ma+1<V.size()/L) return;
	
	vector<int> V2;
	FOR(i,V.size()) {
		if(i==id) continue;
		if(CP[i]==cand) x=i;
		else V2.push_back(V[i]);
	}
	P.push_back({V[id],V[x]});
	dfs(V2,L-1);
	P.pop_back();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	rsrc=mt19937(time(NULL));
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i+1]>>B[i+1]>>C[i+1];
	
	FOR(i,60) {
		vector<int> V;
		FOR(j,N) V.push_back(j+1);
		dfs(V,K);
	}
	cout<<"NO"<<endl;
}

まとめ

乱択回数をこんなギリギリに選択しなければいけないコードは本番は怖すぎて使えない。