計算量で変な勘違いした。
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は厳しいな…」とずっと悩んでしまった。