最近Codeforcesで似た問題を見ていたので解けた。
http://yukicoder.me/problems/105
問題
N要素の数列A[i]が与えられる。
なお、A[i]は乱数で生成される。
ここでQ個のクエリq[i]が与えられる。
各クエリにおいて、q[i]*A[j]%100003の最大値を答えよ。
解法
q[i]==0の時はq[i]*A[j]==0一択、これは例外ケースとする。
それ以外の場合、解法としてはNの大小で分岐させると良い。
- Nが小さい場合、q[i]*A[j]%100003を総当たりしてよい。O(N*Q)で間に合う。
- Nが大きい場合、q[i]*A[j]の候補cを100002、100001、100000、99999…と順に試す。c/q[i]と一致するA[j]があるか順に試せばよい。
- 条件を満たすA[j]の存在確率はN/100003程度なので、Nがある程度以上大きければ100個位cを探す間に解が見つかることが推測できる。
この問題はAが乱数生成なのがミソ。
だからこそ、A[j]は100003個の間に概ね均等にばらまかれていることが期待できる。
unsigned xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123; unsigned xor128() { unsigned t = xor128_x ^ (xor128_x << 11); xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w; return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8)); } ll mo=100003; ll N,Q,A[100030]; ll has[100030]; ll modpow(ll a, ll n) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) { A[i]=xor128()%mo; has[A[i]]++; } while(Q--) { cin>>x; if(x==0) { cout<<0<<endl; continue; } if(N<=100) { y=0; FOR(i,N) y=max(y,(int)(A[i]*x%mo)); } else { ll rev=modpow(x,mo-2); for(y=100002;y>=0;y--) if(has[y*rev%mo]) break; } cout<<y<<endl; } }
まとめ
乱数生成の問題は、単に巨大な入力を生成するためという場合もあるけど、このように分布が偏らないことを意味する場合があるね。