Codeforces #566 Div2 F. Maximum Sine

いやこれは思いつかん。
https://codeforces.com/contest/1182/problem/F

問題

有理数p/qと正整数の区間[a,b]が与えられる。
区間内の整数xのうち、abs(sin(p/q*πx))が最大となるxを求めよ。

解法

abs(sin(p/q*πx))が最大となるには、p/q*πx mod πがπ/2に近ければよい。
さらに式変形すると、px mod 2qがqに近くなれば良い。

あとはBaby Step Giant Stepを応用して解く。
例えばD=√(b-a)とする。
a≦x＜a+Dに対してpx mod 2qを列挙し、昇順にソートしておく。
あとはxをDずつずらすわけだが、a+kD≦x＜a+(k+1)Dの範囲でpx mod 2qがqに近いものを求めるということは、最初に求めたa≦x＜a+Dに対するpx mod 2qから、(q-kD) mod 2qに近いものを探せばよく、これはlower_bound等で高速に求められる。

int T;
ll A,B,P,Q;
ll D=33333;
ll C;
void check(ll b) { // b is better?
	ll x=2*P*C%(2*Q);
	ll y=2*P*b%(2*Q);
	if(abs(Q-y)<abs(Q-x)) C=b;
	if(abs(Q-y)==abs(Q-x)) C=min(C,b);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>P>>Q;
		ll g=__gcd(P,Q);
		P/=g;
		Q/=g;
		P%=Q;

		B++;
		C=A;
		while(A<B && (B-A)%D) {
			check(A);
			A++;
		}
		if(A<B) {
			vector<pair<ll,int>> V;
			unordered_set<ll> S;
			for(x=A;x<A+D;x++) {
				check(x);
				ll v=2*P*x%(2*Q);
				if(S.count(v)==0) {
					S.insert(v);
					V.push_back({v,x-A});
					V.push_back({v-2*Q,x-A});
					V.push_back({v+2*Q,x-A});
				}
			}
			sort(ALL(V));
			for(x=A;x<B;x+=D) {
				ll v=((Q-2*P*(x-A))%(2*Q)+2*Q)%(2*Q);;
				auto it=lower_bound(ALL(V),make_pair(v,0));
				check(x+it->second);
				it--;
				check(x+it->second);
			}
		}
		
		
		cout<<C<<endl;
		
	}
}

まとめ

聞いてしまえばすんなりなんだけど、本番中に思いつく気がしないな。