SRM 616

250

周期がlcm(1,..10)なので2520分後までシミュレーションする。sleepyが減ったら必ず起きられる。
(自分のは実装が少しだけ違います。)

	int maxSleepiness( vector <int> p, vector <int> s, vector <int> v, int D ) {
		ll res = 0,t = 0;
		int n = p.size();
		for(int i = 0; i < n; i++){
			if(p[i]==s[i]) s[i] = 0;
		}
		int D2 = D*2520;
		for(int i = 0; i < n; i++){
			D2 -= v[i]*2520/p[i];
		}
		if(D2<0) return -1;
		for(int i = 1; i <= 125200; i++){
			t -= D;
			for(int j = 0; j < n; j++){
				if(i%p[j]==s[j]) t += v[j];
			}
			res = max(res,t);
		}
		return res;
	}

500

とりあえず割り算すると1回に何枚まで引き出せるかが分かる。(一番金額が高いコインは何枚でも取り出せるから、あまり気にしなくて良い)。K回だけ引き出すとすると、最大a枚取り出せるコインはa^K通りの引き出し方が存在して、合計で1枚は取り出すとすると(a^K)-1通りの引き出し方がある。同じ引き出し方にならないようにすればどのコインか特定できるから、aが小さい方から考えて、(引き出し方)>=(コインの数)であればK回で引き出せることが分かる。(a^K)-1通りの引き出し方があって、aは2以上で、コインの枚数は少ないからKも小さいと分かる。よって、Kを1から順に調べれば良い。

本番では一箇所オーバーフローしてて悲しみ。
(だいぶ汚い実装なのであまり参考にならないと思います)

	int pow(int a, int k){
		int res = 1;
		for(;k;k>>=1){
			if(k&1) res *= a;
			a *= a;
			if(res>100) break;
		}
		return res;
	}
	bool check(int K, vector<P> p){
		int m = p.size();
		ll ms = 1;
		for(int i = 0; i < m; i++){
			int a = p[i].first;
			int b = p[i].second;
			if(pow(a,K)-ms<b) return false;
			ms += b;
		}
		return true;
	}
	int minQueries( vector<long long> vs ) {
		int n = vs.size();
		if(n==1) return 1;
		vector<ll> d(n-1);
		for(int i = 1; i < n; i++){
			d[i-1] = vs[i]/vs[i-1];
		}
		sort(d.begin(),d.end());
		vector<P> p;
		for(int i = 0;i<n-1;){
			int j = i+1;
			ll t = d[i];
			if(t>62) break;
			for(;;){
				if(j==n-1 || t!=d[j]) break;
				j++;
			}
			p.push_back(make_pair(t,j-i));
			i = j;
		}
		for(int i = 1;;i++){
			if(check(i,p)) return i;
		}
	}

ox- 210.28
1852 -> 1910