こちらも3000ptにしては簡単。
http://codeforces.com/contest/1041/problem/F
問題
2つのX軸に平行な直線y=y1とy=y2で挟まれた空間中に反射するレーザーを放つ。
レーザーの放ち方は、両直線上の格子点を1つずつ選び、片方から片方に向けレーザーを放つ。
ここで、両直線上にいくつかの点が存在する。
レーザーを最適に放った場合、最大いくつの点を通過させられるか。
解法
両直前上の点のペアを結ぶようレーザーを放てば最低2点は通る。
よって解の最小値は2である。こうしておくと、真上にレーザーを放つケースを気にしなくてよくなる。
(x,y1)から(x+a*2^b,y2)にレーザーを放ったとする。ただしaは奇数でbは0以上の値とする。
xを十分小さい位置と考えれば、X座標が負の向きにレーザーを放つケースは考えなくてよい。
ここで、aが3以上のケースは考えなくてよい。
なぜなら、(x+2^b,y2)に向けてレーザーを放てば、(x+a*2^b,y2)が通過する直線上の点はすべて通過するためである。
よって、(x,y1)から(x+2^b,y2)にレーザーを放つケースのみ考えればよい。
これは両直線上の点の座標(x,y)をx mod 2^(b+1)で分類して数え上げれば最大値が求められる。
int N,M; ll A[101010],B[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>x; FOR(i,N) cin>>A[i]; cin>>M>>x; FOR(i,M) cin>>B[i]; int ret=2; for(ll L=2;L<=1LL<<40;L<<=1) { map<ll,int> mp; FOR(i,N) mp[A[i]%L]++; FOR(i,M) mp[(B[i]+L/2)%L]++; FORR(m,mp) ret=max(ret,m.second); } cout<<ret<<endl; }
まとめ
今回参加しておけばよかったな。