TopCoder, SRM 629, Division 2, Level 2 : CandyMaking

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13340&rd=16060

問題概要

　 個の容器があり、 番目の容器の容積は である。これらの容器全てを均一な密度の物体で満たしたい。ただし、 番目の容器の内容物の重さは、 に近付けたい。
　容器に入れる物体の密度 を任意に選べるとき、求められている重さと実際の重さの差の和 の最小値を求めよ。

解法

　まず、単一の容器について考えます。密度 から重さの差への関数 を考えると、 は のところで最小値 0 を取り、その両側では線形に増加していきます。また、この関数は自明に（下に）凸です。
　全体では、 個ある関数の和 の最小値を求める問題になります。凸関数の和は凸関数 なので、全体でも凸関数になっています。
　 が連続値をとるため、候補を全て試すことができません。ここでは、 の候補の内、有限な個数だけを調べることで最適解を求められないか考えます。一つ以上の関数が最小値をとる点 を昇順に並べたものを とします。このとき、（有効な に関して）区間 内では全ての関数は線形です。線形関数の和は線形なので、この区間内に限定すれば、区間の端で最小値をとるか、定数関数になっていて区間全体で最小値をとるかのいずれかです。いずれにしても、区間の端点だけ調べれば最小値が分かります。
　上記のような区間の端点となりうる全ての点についてだけ調べれば、全体での最小値を求めることができます。

コード

template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class CandyMaking
{
public:
	double findSuitableDensity( vector <int> containerVolume, vector <int> desiredWeight )
	{
		const int N = containerVolume.size();

		double res = LIM<double>::max();
		REP( i, 0, N )
		{
			const double d = 1. * desiredWeight[i] / containerVolume[i];

			double sum = 0;
			REP( j, 0, N )
			{
				sum += abs( desiredWeight[j] - containerVolume[j] * d );
			}
			res = min( res, sum );
		}
		return res;
	}
};