AtCoder ABC #224 : G - Roll or Increment

こちらはまぁなんとか。
https://atcoder.jp/contests/abc224/tasks/abc224_g

問題

1～Nの目が等確率で出るサイコロがある。
今Sの目が出ており、これをTの目に変えたい。
その際、以下の手順を取ることができる。

• コストをA払い、今出ている目の値を1足す
• コストをB払い、サイコロを振りなおす。

最適手を取るとき、かかるコストの期待値はいくらか。

解法

目をインクリメントした後にサイコロを振りなおす意味はない。
そのため、「Tまでの不足分がX以下なら前者を取り、そうでない場合はその状態になるまで後者を取る」と考える。
この時Xに対するコストの期待値f(X)は下に凸になるので、三分探索をして最小値を求めてもよいし、式から直接最小値を求めてもよい。

ll N,S,T,A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T>>A>>B;
	ll a=(ll)sqrt(2*B*N/A);
	double score=1e30;
	ll best=0;
	
	for(ll x=min(T,a-5);x<=min(T,a+5);x++) {
		if(x<=0||x>T) continue;
		double b=A*(x-1)/2.0+1.0*B*N/x;
		if(b<score) {
			score=b;
			best=x;
		}
	}
	
	if(T-best+1<=S&&S<=T) {
		cout<<A*(T-S)<<endl;
	}
	else {
		_P("%.12lf\n",score);
	}
}

まとめ

解法はすぐ思いつくけど、細部を詰めるのが意外に面倒。