yukicoder : No.691 E869120 and Constructing Array 5

これは思いつかなかった。
https://yukicoder.me/problems/no/691

問題

8000以上12000以下の実数Pが与えられる。
30要素以下の整数列Eのうち、A=sqrt(E[0])+sqrt(E[1])+...としたとき、AとPの差が10^-10未満となるものを構築せよ。

解法

x=1000程度とすると、√(x^2+1)-√(x^2)が5*10^-3程度となる。
これを用いてEを構築しよう。

まず、T=P/8とし、√a+√bとTの差が5e-5以下となるようなものを100個ぐらいつくろう。
これはaは乱数でT^2以下の物を選び、bは対応して和がT前後となるものを選べばよい。
こうして(a,b)の対をたくさん作る。

次に、(a,b)の対を2つ、例えば(a,b)(a',b')を合わせてa+b+a'+b'がP/4との差が5e-7程度となるものを総当たりして探そう。
これにより４要素(a,b,c,d)のタプルが複数できる。

同様に倍々ゲームであと２回許容誤差を小さくしつつ、倍の大きさのタプルを作ることで最終的にAとPとの差が10e-10未満となるような16要素からなる数列Eを構築できる。
これは乱択ベースなので１発でうまくいくとは限らないが、失敗したら(a,b)対の構築からやり直そう。

int Q;
long double A;

vector<int> hoge(long double A) {
	int T2=A/8;
	vector<pair<long double,vector<int>>> C;
	int i;
	while(C.size()<100) {
		int x=rand()%(T2*T2);
		long double B=A/8-sqrt(x);
		int c[2]={(int)(B*B),(int)(B*B)+1};
		FOR(i,2) if(abs(A/8-(sqrt(x)+sqrt(c[i])))<5e-5) C.push_back({sqrt(x)+sqrt(c[i]),{x,c[i]}});
	}
	long double T=A/4, eps=5e-7;
	FOR(i,3) {
		vector<pair<long double,vector<int>>> C2;
		FORR(a,C) FORR(b,C) if(abs(T-(a.first+b.first))<eps) {
			vector<int> V=a.second;
			FORR(v,b.second) V.push_back(v);
			C2.push_back({a.first+b.first,V});
		}
		C=C2;
		T*=2;
		eps *= 1e-2;
	}
	if(C.size()) return C[0].second;
	return vector<int>();
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	srand(time(NULL));
	cin>>Q;
	while(Q--) {
		cin>>A;
		vector<int> V;
		while(1) {
			V=hoge(A);
			if(V.size()) break;
		}
		cout<<V.size();
		FORR(v,V) cout<<" "<<v;
		cout<<endl;
	}
}

まとめ

これは誤差の特性をちゃんと認識してないとダメだね…。