TopCoder SRM 793 : Div1 Easy Div2 Hard GoldMining

EasyもMediumも一発ACしてないので、参加してたら被害大だったかも。
https://community.topcoder.com/stat?c=problem_statement&pm=16617&rd=18345

問題

総量Gの金がある鉱山を掘っていくことを考える。
1人で1日に1の金を掘ることができる。

ここで、時間Tをかけ鉱山の金を掘るとする。
最初は1人で掘るが、途中で掘った金からコストCで人を1人雇うことができる。
この人はその日から同じく1日あたり1の金を追加で掘ってくれる。
コストを賄える金があるなら、一度に複数人雇うことも可能である。

最適手を取ったとき、(得られる金)-(支払うコスト)の最大値を求めよ。

解法

GとCは大きいが、Tは小さい。
また、ある時点でこれ以上人は雇わない、と決めると、以降の採掘量は確定できる。
そこで、経過時間に対してループを行い、毎日所持金の中からできるだけ人を雇ったとし、そのつど最終的な(得られる金)-(支払うコスト)を求めてその最大値を求めよう。

とはいえ、「これ以上雇わなくても鉱山の金はすべて掘り切れる」という場合はそこで止める。
以下のコードでは平方分割の亜種で、雇う人数を1人ずつではなく何段階か飛び飛びにしている。

class GoldMining {
	public:
	long long maxProfit(long long goldInGround, long long miningTime, long long hiringCost) {
		ll ma=min(miningTime,goldInGround);
		ll cur=0;
		ll lef=goldInGround;
		ll step=1;
		int i;
		FOR(i,miningTime) {
			vector<int> steps={100000000, 1000000,1000,1};
			FORR(s,steps) {
				while(hiringCost<=1000000000000000000LL/s&&cur>=s*hiringCost&&lef>=(step+s)*(miningTime-i)) {
					step+=s;
					cur-=hiringCost*s;
					ma=max(ma,cur+min(lef,step*(miningTime-i)));
				}
			}
			cur+=min(lef,step);
			lef-=min(lef,step);
		}
		return ma;
		
	}
}

まとめ

微妙にG,Cが大きくて、途中オーバーフローとかやらかしてしまった。
Easyの割に注意点が多い？問題。