SRM 473 500pt: RightTriangle

問題概要

円周上に等間隔にN(<10^6)個の点がばらまかれる。このうちP(<10^5)個を赤く塗る。赤くする点の選び方は、i=0,1,..,P-1の順に、X[i]番目から順に見ていって初めて赤くない点を赤くする。全ての頂点が赤い直角三角形の個数を求める問題。

考えたこと

• (当時はリストを使って実装して二分探索をやってTLEした記憶がある。リストはランダムアクセスが遅いので二分探索が意味を持たない)
• 直角三角形を求めるパートは簡単だ。円周角の定理より中心を通る線を選べば良い。その間にいくつ赤い点があるかは二分探索で求められる。ただしsetのイテレータでdistanceを求めるのは時間がかかるのでvectorでやること。
• 難しいのは色を塗るパートだけど、これもsetに赤くない点を突っ込んでlower_boundで求めてやれば良い。P[i]を求める途中でオーバーフローしないように注意。
• 書けた。無事通った。

practiceで通ったコード

計算量O(N*log N)。

#include <set>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = 1000000;
bool is_red[MAX_N];

struct RightTriangle {

	int64 triangleCount(int places, int points, int64 a, int64 b, int64 c) {
		//奇数は無理
		if(places&1){
			return 0;
		}

		//色塗りパート
		set<int> whites;
		for(int i=0; i<places; i++){
			whites.insert(i);
		}

		for(int i=0; i<points; i++){
			int pn = (a * i * i + b * i + c) % places;

			set<int>::iterator itr = whites.lower_bound(pn);
			if( itr != whites.end() ){
				is_red[*itr] = true;
				whites.erase(itr);
			}
			else{
				is_red[*whites.begin()] = true;
				whites.erase(whites.begin());
			}
		}

		//二分探索用に赤を集める
		vector<int> reds;
		for(int i=0; i<places; i++){
			if(is_red[i]){
				reds.push_back(i);
				reds.push_back(i + places);
			}
		}
		sort(reds.begin(), reds.end());

		//直角三角形探しパート
		int64 ret = 0;
		for(int i=0; i<places; i++)if(is_red[i] && is_red[(i+places/2)%places]){
			vector<int>::iterator lb = lower_bound(reds.begin(), reds.end(), i+1),
					ub = upper_bound(reds.begin(), reds.end(), i+places/2-1);
			ret += distance(lb, ub);
		}
		return ret;
	}

};

他の人の解放

• 直角三角形の数を数える部分では、二分探索ではなくて累積和を利用している人がいた。確かにそっちの方が速い(全体の計算量は変わらないが)。