kmjp's blog

競技プログラミング参加記です

Codeforces #488 Div1 C. Careful Maneuvering

計算量で変な勘違いした。
http://codeforces.com/contest/993/problem/C

問題

2次元座標上でx=-100の位置にN個、x=100の位置にM個の敵機があるとする。
ここでx=0の任意のy座標に2つまで自軍の機体を置くことを考える。

各敵機は、2つの自軍の機体に向けて同時に直線的に向かうレーザーを放つ。
自軍の機体はその際瞬間的に避けることが出来、そうするとその向こうにいる敵機にレーザーが当たり破壊できる可能性がある。

自軍の機体の位置を最適に選んだ場合、最大何個の敵機を破壊できるか。

解法

敵機同士を相打ちさせるには、自軍の機体の位置の候補は高々NM個である。
それぞれのケースで、破壊される敵機をbitmaskで持とう。

あとは候補を2つ選択し、bitmaskのorを取ればよい。
ビット並列化によりO(N^2*M^2*(N+M)/w)で解くことができる。

int N,M;
int X[61];
int Y[61];

vector<pair<ll,ll>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>X[i];
	FOR(i,M) cin>>Y[i];
	
	vector<pair<ll,ll>> V;
	for(i=-20000;i<=20000;i++) {
		ll ma=0,mb=0;
		FOR(x,N) FOR(y,M) if(X[x]+Y[y]==i) {
			ma |= 1LL<<x;
			mb |= 1LL<<y;
		}
		if(ma || mb) {
			V.push_back({ma,mb});
		}
	}
	
	int ret=0;
	FORR(v1,V) FORR(v2,V) {
		ret=max(ret,__builtin_popcountll(v1.first | v2.first) + __builtin_popcountll(v1.second | v2.second));
	}
	cout<<ret<<endl;
	
	
}

まとめ

ビット並列化が思い浮かばず「60^5は厳しいな…」とずっと悩んでしまった。