SRM 399 250pt: AvoidingProduct

TopCoder

問題概要

整数集合A(<50)と整数N(<=1000)が与えられる。x,y,zの組でx,y,z not in Aの条件下でx*y*zとnの差を最小化する辞書順最小なものを求める問題。

考えたこと

  • 全探索は1000^3だけどこれは処理軽いから行ける気がする。
  • でも上限1000じゃないのか、まあ2000位まで調べてやれば大丈夫だろう。あと数が大きくなりすぎたら適当に打ちきるとか。
  • あとは書くだけ。無事通った。
  • 予想通り1000までしか調べてない解答がそこそこあったので撃墜しておいた。

practiceで通ったコード

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1000;
const int INF = 1<<29;

bool bad[3*MAX_N];

struct AvoidingProduct {

	vector <int> getTriple(vector <int> a, int n) {
		vector<int> ret(3);

		for(int i=0; i<(int)a.size(); i++){
			bad[a[i]] = true;
		}

		int dist = INF;
		for(int x=1; x<=MAX_N; x++)if(!bad[x]){
			for(int y=x; y<=MAX_N; y++)if(!bad[y] && x * y < n + dist){
				for(int z=y; z<=2 * MAX_N; z++)if(!bad[z] && abs(n - x*y*z) < dist){
					dist = abs(n - x* y * z);
					ret[0] = x; ret[1] = y; ret[2] = z;
				}
			}
		}

		return ret;
	}

};