TopCoderOpen 2019 Round1A Hard EllysTicketPrices

何だこの問題…。
https://community.topcoder.com/stat?c=problem_statement&pm=15340

問題

N日間のチケットの平均販売額を考える。
i日目の価格をP(i)と表現することとする。
前日との差分C[i]が配列として与えられる。

i日目の価格に対し、翌日の価格はC[i]パーセントだけ増加(C[i]が負なら減少)した価格となる。
ただし、増減の計算の結果、小数点以下第２位までに四捨五入される。
また、N日間の平均額を求める際も、小数点以下第２位までに四捨五入される。

平均価格をTにしたい場合、初日の金額を最低いくらにすべきか。

解法

初日の価格が増せば平均額も増すので、二分探索で良い。
あとは初日の価格が定まったときの各日の価格と平均価格を間違えないように処理しよう。

小数のまま扱うと誤差で誤りやすいので、全体を100倍してしまおう。
そうすると増減も平均額も結局は整数で処理すればよいことになる。
また、四捨五入する場合は直前に除算があるので、剰余の値を覚えておけば四捨五入も正確に行える。

class EllysTicketPrices {
	public:
	double proc(ll cur,vector <int> C) {
		int i,j;
		ll sum=cur;
		FOR(j,C.size()) {
			ll c=cur*(100+C[j]);
			cur=c/100+(c%100>=50);
			sum+=cur;
			if(sum>1LL<<30) return 1LL<<30;
			
		}
		int N=C.size()+1;
		sum=sum/N+(sum%N*2>=N);
		return sum;
	}
	
	double getPrice(int N, vector <int> C, int target) {
		double L=0,R=1<<30;
		int i,j;
		target*=100;
		while(R-L>1) {
			ll M=(L+R)/2;
			if(proc(M,C)<target) L=M;
			else R=M;
		}
		
		return R/100.0;
		
	}
}

まとめ

MediumもHardもミスしてたので、出てたらひどいことになってた。