yukicoder : No.814 ジジ抜き

気づけば実装は簡単。
https://yukicoder.me/problems/no/814

問題

N個の等差数列が与えられる。
このうちある1つだけ、一連の等差数列中に奇数回登場するものがあるので、それを求めよ。

解法

ある整数Vに対し、各等差数列にV以下の整数が何個あるかはO(N)で求められる。
よってその値が奇数となる最小のVを二分探索すればよい。

int N;
ll K[303030],L[303030],D[303030];

ll hoge(ll v) {
	ll tot=0;
	int i;
	FOR(i,N) if(v>=L[i]) {
		if(L[i]+(K[i]-1)*D[i]<=v) {
			tot+=K[i];
		}
		else {
			tot+=1+(v-L[i])/D[i];
		}
	}
	return tot;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>K[i]>>L[i]>>D[i];
		D[i]=1LL<<D[i];
	}
	
	ll ma=-1;
	for(i=60;i>=0;i--) if(hoge(ma+(1LL<<i))%2==0) ma+=1LL<<i;
	cout<<ma+1<<endl;
	
}

まとめ

これ出てたら解けてなさそう。