TopCoder SRM 399 Div1 Easy AvoidingProduct

問題

整数nが与えられる。自然数x,y,zを、

n-x*y*z

が最小になるようかつ、x,y,zがa[]の要素のどれとも一致しないように選べ。

ただし、そのようなx,y,zの組が複数ある場合、
xが最小になるように、それも複数ある場合yが最小になるように、それも複数ある場合zが最小になるように選べ。

制約条件

n≦1000
aの要素の数≦1000
a[i]≦1000

方針

xとyを決め打ちすると、最適なzは一つか二つにしぼれる。
zが、a[]の要素と一致し続ける間+1し続けるor-1しつづければ、
そのx,yに対する最適なzが求まる。

これをx,yについてそれぞれ1050くらいまで回せばよい。

ソースコード

bool ng[1100];
int ax,ay,az,d;
void ck(int n,int x,int y,int z){
  int cd=abs(n-x*y*z);
  if(cd<d||cd==d&&(x<ax||x==ax&&y<ay||x==ax&&y==ay&&z<az))
    d=cd, ax=x, ay=y, az=z;
}
class AvoidingProduct {
  public:
  vector <int> getTriple(vector <int> a, int n) {
    memset(ng,0,sizeof(ng));
    rep(i,a.size())ng[a[i]]=1;
    
    d=inf;
    for(int x=1;x<=1050;x++)for(int y=1;y<=1050;y++){
      if(ng[x]||ng[y])continue;
      int tz=n/(x*y), z;
      
      for(z=tz+1;ng[z];z++);
      ck(n,x,y,z);
      for(z=tz;z>0&&ng[z];z--);
      if(z>0)ck(n,x,y,z);
    }
    vi ans;
    ans.pb(ax); ans.pb(ay); ans.pb(az);
    return ans;
  }
};