TopCoder SRM 629 Div2 Hard CandyAddict

アプローチはすぐ思いついたがバグ修正に手間取った。
http://community.topcoder.com/stat?c=problem_statement&pm=13345

問題

プレイヤーは初期状態で0個の飴と所持金0円を持つ。
毎日プレイヤーは以下の処理を以下の順で行う。

1. 所持金がX円増える。
2. 飴を１個も持ってなければ、所持金で買えるだけ１個Y円の飴を買う。
3. 飴を１個食べる。

Z日目終了後にプレイヤーが持つお金はいくらか。
なお、X>=Yなので飴を食べられないことはない。

解法

• X==Yの時は毎日１個飴を買いお金が0円になる。
• X>=2Yの時は容易である。
  • p個の飴を消費している間に2p個以上飴を買うお金が手に入るので、飴を買うのは高々O(logZ)回で済む。
  • よって素直に飴を買うシミュレーションを行えばよい。
• X<2Yの時は、飴を買うたびに買える飴の数が増えない。
  • よって、次に買える飴の数が増えるのはいつか、という観点でシミュレートすればよい。
  • たとえば今毎回１個しか飴を買えない場合、飴を買うたびに(X-Y)円ずつ所持金が増えるのでY/(X-Y)日立てば２個ずつ飴を買えるようになる。
  • １度に買える飴の数Sが増え、S(X-Y)>Yになると、飴を買える量が毎回増えていくので、あとはX>=2Y同様にシミュレートすれば良い。毎回買える飴の数が少しずつ増えるので、愚直にシミュレートしてもO(√N)で済む。

class CandyAddict {
	public:
	ll dodo(ll X,ll Y,ll Z){
		if(X==Y) return 0;
		ll C=0,NC=0;
		
		while(X<=2*Y && Z>0) {
			ll S=(C+X)/Y;
			ll NS=((C+X)%Y+S*X)/Y;
			if(NS>S+1) break; // 1 loop inc NC
			if(S==NS) {
				ll sd=S*X%Y;
				ll st=(Y-(C+X)%Y+(sd-1))/sd;
				if(Z<=st*S) return C+Z*X-(Z+(S-1))/S*S*Y;
				Z-=st*S;
				C = C+st*S*(X-Y);
			}
			else {
				if(Z<=S) return C+Z*X-S*Y;
				Z-=S;
				C=C+S*(X-Y);
			}
		}
		
		while(Z>0) {
			C+=X;
			NC=C/Y;
			C%=Y;
			if(Z<=NC) return C+(Z-1)*X;
			Z-=NC;
			C+=X*(NC-1);
		}
	}
	vector<long long> solve(vector <int> X, vector <int> Y, vector <int> Z) {
		vector<ll> V;
		int i;
		FOR(i,X.size()) V.push_back(dodo(X[i],Y[i],Z[i]));
		return V;
	}
}

まとめ

問題設定がややこしいけど、XとYの大小関係でアプローチが変わるのは面白い。