kmjp's blog

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

yukicoder : No.97 最大の値を求めるくえり

最近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;
	}
}

まとめ

乱数生成の問題は、単に巨大な入力を生成するためという場合もあるけど、このように分布が偏らないことを意味する場合があるね。