Codeforces #538 Div2 E. Arithmetic Progression

まんまと狙い撃ちされた。
https://codeforces.com/contest/1114/problem/E

問題

ある長さNの数列がある。
この数列を昇順に並べ替えると等差数列になり、公差は正で、数列の値は0～10^9の範囲であるとする。

以下の２つのクエリを計60回用いて、初項と公差を求めよ。

• iを指定すると、i番目の要素を返す
• 整数xを指定すると、xより大きな値があるかどうかの真偽値を返す

解法

後者のクエリを用いて二分探索すると、最後の項の値がわかる。
あとは乱択で30個程度の要素を選ぼう。差のGCDを取れば高確率で交差となる。

ただ問題は乱択で、CodeforcesのGCCのrand関数はRAND_MAXが(2^15)-1と小さい。
狙い撃ちもされやすいので、もっと周期が長く値が予測しづらいものを選ぼう。

int N;
int ask1(int cur) {
	int ret;
	cout<<"? "<<cur<<endl;
	cin>>ret;
	return ret;
}
int ask2(int cur) {
	int ret;
	if(cur>1000000000) return 0;
	cout<<"> "<<cur<<endl;
	cin>>ret;
	return ret;
}
void ans(ll X,ll D) {
	exit(0);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	std::mt19937 mt{ std::random_device{}() };
	cin>>N;
	ll ma=-1;
	for(i=29;i>=0;i--) if(ask2(ma+(1<<i))) ma+=1<<i;
	ma++;
	
	vector<ll> V;
	V.push_back(ma);
	FOR(i,30) V.push_back(ask1(mt()%N+1));
	
	
	ll MD=0;
	FORR(x,V) FORR(y,V) if(x!=y) MD=__gcd(MD,abs(x-y));
	
	cout<<"! "<<(ma-(N-1)*MD)<<" "<<MD<<endl;
	
}

まとめ

うーん、これで落ちるのは面白くないなぁ。