torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder SRM 634, Division 1, Level 1 : ShoppingSurveyDiv1

問題概要

 ある店では M 種類の商品を販売している。
 N 人の顧客について、それぞれが購入した商品のリストを作成した。なお、各顧客は同じ品物は高々一つしか購入しない。また、全く何も買っていないということも有り得る。その後、各商品について、販売数の合計値を算出した。i 番の品物の販売数の合計は s_i である。合計値の算出後、元のリストを紛失してしまった。
 顧客について、K 種類以上の商品を購入した顧客を big shopper と呼ぶとする。顧客の人数 N 、定数 K 、及び各商品の販売数 s のみが与えられたとき、big shopper の人数の最小値を求めよ。
 N \leq 500

解法

 各商品について、その購入者を任意に割り振ることができます。big shopper の数を最小化したいので、全種類買ってしまう顧客が発生しないように割り振ることを考えます。
 N の最大値があまり大きくないので、big shopper の数を全通り仮定することができそうです。big shopper の人数をある値に固定した条件下で、そのような割り振りが可能か否かを(余り遅すぎない実行時間で)判定することができれば問題を解けます。
 さて、仮定した big shopper の人数を b として、その割り振りが可能か否かを求める方法を考えます。big shopper になる b 人には、できるだけ多くの商品を買っておいてもらった方が、残りの顧客が買わなければならない品物の数が減って得になります。従ってまず、各商品の販売数から一律に b を減じます。このとき、0 を下回る場合は 0 にクリッピングします。残りの品物については、残りの顧客の購入数の最大値を最小化すると考えます。残りの顧客に均等に割り振った方がよいので、残った商品の数の総和を a とすれば、\lceil \frac{ a }{ N - b } \rceil < K を満たすとき、適当な割り振りで残った顧客が買う品物の最大値を K 未満にできます。
 あとは仮定する b を小さい方から順に試せば、最初に条件を満たしたものが答えだと分かります。

コード

using VI = vector<int>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class ShoppingSurveyDiv1
{
public:
	int minValue( int N, int K, vector <int> s )
	{
		REP( i, 0, N )
		{
			if ( ok( N, K, s, i ) )
			{
				return i;
			}
		}
		return N;
	}

	bool ok( const int N, const int K, VI s, const int big )
	{
		const int rest = N - big;

		transform( ALL( s ), s.begin(), [&]( const int a ){ return max( 0, a - big ); } );
		return ( accumulate( ALL( s ), 0 ) + rest - 1 ) / rest < K;
	}
};