Codeforces #226 Div2. D. Bear and Floodlight

幾何問題。なんとか本番正答できてよかった。
http://codeforces.com/contest/385/problem/D

問題

２次元座標上、(L,0)から(R,0)まで移動したい。
しかし周りが暗く、そのままでは移動することができない。

そこで、上空にあるN個のライトを利用する。
各ライトは上空(X[i],Y[i])に配置されており、角度A[i]の範囲を照らすことができる。
これによりX軸上を照らすと、その範囲は移動可能になる。

ライトの向きは最初に指定すると以後変更できない。
適切なライトの向きを選択した場合、(L,0)から(R,0)にたどり着けるか、たどり着けないなら最大どこまで移動できるか答えよ。

解法

N<=20なので、明らかにBitDPを前提としているのだろう。

各ライトの使用有無をbitmaskで表現してbitDPしていく。
使用済みライトにより現在移動可能な右端のX座標に対し、未使用なライトが照らす範囲がその移動可能右端の座標となるようにライトの角度を選択し、さらにどこまで右側に移動できるか求めればよい。

ライト角度によっては、無限遠まで照らせる場合があり、その時はもちろん(R,0)も到達可能である。

int N,L,R;
int X[100],Y[100];
double A[100];
double dest[1<<20];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>L>>R;
	R-=L;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>x;
		X[i]-=L;
		A[i]=atan(1)*x/45;
	}
	
	for(int mask=0;mask<1<<N;mask++) {
		FOR(i,N) if((mask & (1<<i))==0) {
			double dx=dest[mask]-X[i];
			double dy=-Y[i];
			double ex=dx*cos(A[i])-dy*sin(A[i]);
			double ey=dx*sin(A[i])+dy*cos(A[i]);
			if(ey>=0) return _P("%d\n",R);
			double tx=X[i]-Y[i]*ex/ey;
			dest[mask|(1<<i)] = max(dest[mask|(1<<i)], tx);
			if(dest[mask|(1<<i)]>R) return _P("%d\n",R);
		}
	}
	
	_P("%.12f\n",dest[(1<<N)-1]);
}

まとめ

あまりややこしくない幾何で助かった。