問題
http://community.topcoder.com/stat?c=problem_statement&pm=8758&rd=12171
解き方
zの探索を枝刈りすることによって、ほぼx,yのすべての組み合わせだけ調べればよいので
O(10^6)で全探索可能。
調べる範囲として、NGの値の上限は1000のため取りうる値は1001まで
調べる必要がある。上限値の設定によるエラーケースに注意。
コード
class AvoidingProduct {
public: vector<int> getTriple(vector<int> a, int n) {
set<int> s;
FORE(i,0,a.size())s.insert(a[i]);
vector<int> ans(3,1001);
for(int x=1;x<=1001;x++)if(s.find(x)==s.end()){
for(int y=x;y<=1001;y++)if(s.find(y)==s.end()){
for(int z=y;z<=1001;z++)if(s.find(z)==s.end()){
int cur=abs(ans[0]*ans[1]*ans[2]-n);
if(cur>abs(x*y*z-n)){
ans[0]=x,ans[1]=y,ans[2]=z;
}
if(abs(x*y*z-n)> abs(x*y*(z-1)-n))break;
}
}
}
return ans;
}
};
public: vector<int> getTriple(vector<int> a, int n) {
set<int> s;
FORE(i,0,a.size())s.insert(a[i]);
vector<int> ans(3,1001);
for(int x=1;x<=1001;x++)if(s.find(x)==s.end()){
for(int y=x;y<=1001;y++)if(s.find(y)==s.end()){
for(int z=y;z<=1001;z++)if(s.find(z)==s.end()){
int cur=abs(ans[0]*ans[1]*ans[2]-n);
if(cur>abs(x*y*z-n)){
ans[0]=x,ans[1]=y,ans[2]=z;
}
if(abs(x*y*z-n)> abs(x*y*(z-1)-n))break;
}
}
}
return ans;
}
};