TopCoder SRM 812 : Div1 Easy Div2 Hard GuessForMoney

これはEasyにしてもひねりがない…？
https://community.topcoder.com/stat?c=problem_statement&pm=17108&rd=18805

問題

正整数Nが与えられる。
0～(N-1)のいずれかの数がランダムで選ばれたとき、それを当てるゲームを考える。
1つ値を選択すると、当てる対象の数と比べ

• 一致する
• 小さい
• 大きい

のいずれかが返される。
最適な手順で値を選択するとき、一致するまでに必要な最小選択回数の期待値を求めよ。

解法

2分探索することを考えると、求める値をf(N)としたとき

となる。あとはメモ化再帰すればよい。

map<ll,double> memo;

class GuessForMoney {
	public:
	double balance(long long N) {
		if(memo.count(N)) return memo[N];
		if(N<=1) return N;
		double a=N/2;
		double b=N-a-1;
		double ret=1+a/N*balance(a)+b/N*balance(b);
		return memo[N]=ret;
	}
}

まとめ

Div2でも900ptだしね。