TopCoder SRM 742 Div1 Easy, Div2 Hard ResistorFactory

なんとかレート増をキープしたが、Mediumの無駄ResubmitやHardをもうちょっとで落とすなど色々惜しい回。
https://community.topcoder.com/stat?c=problem_statement&pm=15226

問題

以下だいぶ意訳。

実数集合Sを考える。初期状態でS={1}である。
S中の2要素（同一要素を複数回使うこともできる）選び、その和または調和平均をSに加える、ということを行える。
実数Rが与えられるので、SにR±10^-9の範囲の実数を追加するまでの手順の一例を答えよ。

解法

同じ値同士の和または調和平均を取ると、元の値の倍もしくは半分をSに加えることができる。
そこで、1から2の累乗を10^-9～10^9程度まで作ろう。
あとは和がRになるようにこれらの一部を足しこんでいけばよい。

他に二分探索解もある。
Sからa,bを選んで和(a+b)を作り、(a+b)同士の調和平均を取ることで(a+b)/2を作ることができる。
よって、最初に非常に大きい値と小さい値を作り、あとは二分探索してRに近づけることもできる。

class ResistorFactory {
	public:
	vector <int> construct(long long nanoOhms) {
		double D=nanoOhms/1e9;
		double V[200]={};
		vector<int> R,R2;
		
		int i;
		V[0]=1;
		for(i=1;i<100;i++) {
			R.push_back(i-1);
			R.push_back(i-1);
			R.push_back(0);
			V[i]=V[i-1]*2;
		}
		R.push_back(0);
		R.push_back(0);
		R.push_back(1);
		V[100]=0.5;
		for(i=101;i<200;i++) {
			R.push_back(i-1);
			R.push_back(i-1);
			R.push_back(1);
			V[i]=V[i-1]*0.5;
		}
		
		for(i=99;i>=0;i--) {
			if(D>=V[i]) {
				R2.push_back(i);
				D-=V[i];
			}
		}
		for(i=100;i<199;i++) {
			if(D>=V[i]) {
				R2.push_back(i);
				D-=V[i];
			}
		}
		R2.push_back(199);
		
		for(i=1;i<R2.size();i++) {
			if(i==1) {
				R.push_back(R2[0]);
				R.push_back(R2[1]);
				R.push_back(0);
			}
			else {
				R.push_back(R.size()/3);
				R.push_back(R2[i]);
				R.push_back(0);
				
			}
		}
		return R;
		
		
	}
}

まとめ

2の累乗が作れることに気づけばすぐだね。
Div2 Hardでこれが誰にも解かれないのは意外。