Kodamanと愉快な仲間たち : V - Constellation 3

方針は割とすぐ立つけど、そこからの定数倍高速化に手間取った。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/constellation-3

問題

H*Wのグリッドが与えられる。
各セルは赤青緑色のいずれかで塗られている。
赤・青・緑色のセルを1個ずつ選ぶとき、各セルの中心を結んだ三角形の面積の期待値を求めよ。

解法

赤と青のセルを選んだ時、他の全緑セルを選んだ時の三角形の面積の総和を考える。
緑セルを1個選ぶと、赤→青セルと赤→緑セルのベクトルの外積の絶対値から三角形の面積が求められる。
全緑セルに対して、X座標の総和とY座標の総和を持っておけば一気に全緑セル分の面積の総和が取れるか…というと絶対値のせいでうまくいかない。
絶対値を取る際符号反転が必要かどうかは、緑セルが赤→青セルを見る向きに対し左側か右側かによる。

そこで、赤セルを総当たりし、他の色のセルを偏角ソート後順次見ていく。
対象の赤セルからX座標正方向に伸びる走査線が、左回りに回転して1周していき、青セルや緑セルにあたるたびに処理していくことを考える。
青いセルに走査線が当たったとき、上記X座標とY座標の総和を元に面積の総和を計算していく。
緑セルにあたると、そのセルは符号反転の有無が反転する。

微妙にTLが厳しいので、上記手順で赤・青・緑の順で処理が重いため、登場頻度の少ない色を重い処理に割り当てるようにしよう。

int H,W;
string S[106];
pair<int,char> P[3];

double A[300][300];
int B[300][300];
int num[30000];
int cand[30000][115][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	double pi=atan(1)*4;
	
	P[0].second='R';
	P[1].second='G';
	P[2].second='B';
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FORR(c,S[y]) {
			FOR(i,3) if(c==P[i].second) P[i].first++;
		}
	}
	sort(P,P+3);
	
	if(P[0].first==0) return _P("-1\n");
	
	vector<double> V;
	for(y=-H;y<=H;y++) for(x=-W;x<=W;x++) if(x||y) {
		int g=__gcd(abs(y),abs(x));
		V.push_back(atan2(-y/g,x/g));
		if(V.back()<0) V.back()+=2*pi;
		A[150+x][150+y]=V.back();
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	for(y=-H;y<=H;y++) for(x=-W;x<=W;x++) if(x||y) {
		B[150+x][150+y]=lower_bound(ALL(V),A[150+x][150+y])-V.begin();
	}
	
	
	ll ret=0;
	
	FOR(y,H) FOR(x,W) if(S[y][x]==P[0].second) {
		int sx=0,sy=0,nx=0,ny=0;
		int y2,x2;
		FOR(y2,H) FOR(x2,W) {
			if(S[y2][x2]==P[1].second) {
				
				i=B[x2-x+150][y2-y+150];
				j=B[x-x2+150][y-y2+150];
				cand[i][num[i]][0]=2;
				cand[j][num[j]][0]=1;
				cand[i][num[i]][1]=cand[j][num[j]][1]=x2-x;
				cand[i][num[i]][2]=cand[j][num[j]][2]=y2-y;
				num[i]++;
				num[j]++;
				
				sx+=(x2-x);
				sy+=(y2-y);
				if(y2>y || (y2==y && x2<x)) {
					nx+=(x2-x);
					ny+=(y2-y);
				}
			}
			if(S[y2][x2]==P[2].second) {
				i=B[x2-x+150][y2-y+150];
				cand[i][num[i]][0]=0;
				cand[i][num[i]][1]=x2-x;
				cand[i][num[i]][2]=y2-y;
				num[i]++;
			}
		}
		
		FOR(i,V.size()) {
			FOR(j,num[i]) {
				if(cand[i][j][0]==0) {
					ret+=cand[i][j][2]*(sx-2*nx)-cand[i][j][1]*(sy-2*ny);
				}
				if(cand[i][j][0]==2) {
					nx+=cand[i][j][1];
					ny+=cand[i][j][2];
				}
				if(cand[i][j][0]==1) {
					nx-=cand[i][j][1];
					ny-=cand[i][j][2];
				}
			}
			num[i]=0;
		}
		
	}
	
	double R=ret/2.0;
	FOR(i,3) if(P[i].first>0) R/=P[i].first;
	_P("%.12lf\n",R);
	
}

まとめ

作者がバラバラなためか、問題文や解説の形式もバラついているな…。