読者です 読者をやめる 読者になる 読者になる

むぅ。

404 Not Found

を解いていて久々にリアルに紙を使った。

1.最初に置くロールケーキの中心座標は、箱の左端をx座標の0、床をy座標の0だとして、{ ¥normal(x,y)=(r,r)}である。

2.どのロールケーキもy座標は床からの高さである(問題文から)。

3.よって、判明していないのは、片方のロールケーキのx座標であるので、それを求める方程式を作れば良い。

4.ということで考えてたら、隙間ができないような置き方は、円1と円2の中心のユーグリッド距離がちょうど「(円1の半径)+(円2の半径)」となるようなx2を取る置き方だということに気づく。(くっついてるってことはそういうこと)

5.方程式つくって解く。

{¥large ¥sqrt{(x{¥small 1}-x{¥small 2})^2+(r{¥small 1}-r{¥small 2})^2}=r{¥small 1}+r{¥small 2}}

{¥large (x{¥small 1}-x{¥small 2})^2+(r{¥small 1}-r{¥small 2})^2=(r{¥small 1}+r{¥small 2})^2}

{¥large =X^2-2xX+x^2-4r{¥small 1}r{¥small 2}}(可読性のためx{¥small 1}xx{¥small 2}Xと置いています。)


そしてX(x{¥small 2})について解の公式を使って解く。

X = ¥frac{-(-2x)¥pm¥sqrt{(-2x)^2-4(x^2-4r{¥small 1}r{¥small 2})}}{2}

マイナスする方は使わないので+のほうとる。

とまあそんな感じでやってました。数学苦手なのでよく分からないです。TeXとか使って気取ってみたけど。

で、これを元に色々バックトラックとかやったけどTLEしまくる。効率が悪いっぽい。どうすりゃいいんだと諦め中。数字の範囲が7なのにnの上限は12だったりと枝狩りできそうでやったけど、意味無かったし。DPとかするのかな?

残骸ソース

#include <iostream>
#include <sstream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second

vector<double> data;
pair<double,double> lc;
vector<bool> done;

int boxSize;
bool flag;

double solve(double x,double a,double b){
	return (2.0*x+sqrt(4*x*x-4*(x*x-4*a*b)) ) / 2.0;
}

void bt(){
	if( count(done.begin(),done.end(),true) == done.size() ){
		if( lc.X + lc.Y<=boxSize){
			flag = true;
		}
	}
	//if(flag || lc.X + lc.Y > boxSize)return;
	
	for(int i=0;i<data.size();i++){
		if(done[i])continue;
		
		if(solve(lc.X,lc.Y,data[i]) > boxSize)continue;
		done[i] = true;
		pair<double,double> tmp = lc;
		lc = make_pair(solve(lc.X,lc.Y,data[i]),data[i]);
		bt();
		lc = tmp;
		done[i] = false;
	}
}


int main(){
	int t;
	string s;
	while(getline(cin,s) && s != ""){
		vector<int> input; data.clear();
		flag = false;
		stringstream ss(s);
		while(ss >> t)input.push_back(t);
		boxSize = input[0];
		for(int i=1;i<input.size();i++)data.push_back(input[i]);
		done.resize(data.size()); fill(done.begin(),done.end(),false);

		for(int i=0;i<data.size();i++){
			done[i] = true;
			lc = make_pair(data[i],data[i]);
			bt();
			done[i] = false;
		}
		cout << (flag?"OK":"NG") << endl;
	}
}

そもそも解法が間違っているという可能性もある。