TCO14 Algo 1C hardを解いてみた

昨日の記事、TCO14 Algo 1C - やざてんのいろいろの追記です。

hardの感想で「わかりませんでした。」 とか言ってたら、わざわざ解法を教えて下さった方がいたので解きました。

解法

移動した回数(N)に対する期待値を試しに N=0～6 まで計算してみると、「1, 2, 2.5, 3, 3.75, 4.0625, 4.375」となり、それぞれの値を求める式は x(N)=x(N-1)+gapとなる。
また、このgapは1から始まり、Nが2で割り切れる値になる度に「gap*=(N-1)/N」で更新される。
これをN回繰り返し計算すれば良い。

using namespace std;

class RedPaint{
public:
	double expectedCells(int N){
		double ans[501]={1},gap=1;
		
		for(int i=1;i<=N;i++){
			if(i%2==0)gap *= ( (double)(i-1)/(double)i );
			ans[i]=ans[i-1]+gap;
		}
		return ans[N];
	}
};

• 実はうまいアルゴリズムが思いつかなかったので、自分でもN=0～4まで調べていた。増加量が「1, 1, 0.5, 0.5 0.375」となっていたので、なにか漸化式っぽいものが立てられそうだな～と思ったが思いつかず諦めていた。

• コメントを頂いた方も言っていたが、いまいち証明ができない解法を使うのはモヤモヤするので、dp解法もいずれ解いておきたい。