2014-02-17

■ SRM 522 Div1 Medium 01:51

50問に1回くらい見るレベルの良問だと思いました。

問題:

正整数a,b,cが与えられる。(a,b,c<=10^9)

このとき|A-a|+|B-b|+|C-c|の最小値を求めなさい。

ただし、A,B,CはA*B=Cを満たす正整数とする。

解法:

Cの候補を絞ることを考えると、

実はmax(1,c-3*sqrt(10^9)/2)~c+3*sqrt(10^9)/2くらいを調べておけば良いと分かる。

なぜなら、A*B=CよりA,Bのいずれかはsqrt(C)以下であるため、

その相方をうまく調節すればCとcをsqrt(C)/2以下の差にすることができるはずである。

また、必ず最小値は2*10^9は下回るため(2*10^9回もあればa,bを好きなように変更できるので)

C<=c+2*10^9<=3*10^9となり、正当性が示せた。

あとはこの候補に対しA,Bを求めればよいが、愚直にやるとsqrt(10^9)*sqrt(10^9)=10^9となり死ぬ。

しかし今回はA=1の時の対応するB、A=2の時の対応するB...のみを順に見ることが可能であり、

そうするとsqrt(10^9)*(1/1+1/2....1/sqrt(10^9))=sqrt(10^9) log sqrt(10^9)となり間に合う。

class CorrectMultiplication
{
	public:
	long long getMinimum(int a, int b, int c) 
	{
		ll ret=INF;
		int lb=max(1,c-50000);
		int ub=c+50000;
		for(int i=1;i<=50000;i++)
		{
			int x=(lb+i-1)/i;
			for(int j=i*x;j<=ub;j+=i)
			{
				ret=min(ret,1LL*abs(i-a)+1LL*abs(j/i-b)+1LL*abs(j-c));
				ret=min(ret,1LL*abs(i-b)+1LL*abs(j/i-a)+1LL*abs(j-c));
			}
		}
		return ret;
	}
};

ツイートする