を解いていて久々にリアルに紙を使った。
1.最初に置くロールケーキの中心座標は、箱の左端をx座標の0、床をy座標の0だとして、である。
2.どのロールケーキもy座標は床からの高さである(問題文から)。
3.よって、判明していないのは、片方のロールケーキのx座標であるので、それを求める方程式を作れば良い。
4.ということで考えてたら、隙間ができないような置き方は、円1と円2の中心のユーグリッド距離がちょうど「(円1の半径)+(円2の半径)」となるようなx2を取る置き方だということに気づく。(くっついてるってことはそういうこと)
5.方程式つくって解く。
(可読性のためを、をと置いています。)
そしてについて解の公式を使って解く。マイナスする方は使わないので+のほうとる。
とまあそんな感じでやってました。数学苦手なのでよく分からないです。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; } }
そもそも解法が間違っているという可能性もある。