torus711 のアレ

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

TopCoder, Single Round Match 647, Division 2, Level 2 : TravellingSalesmanEasy

問題概要

 M 個の街があり,その内の幾つかの街に商品を売りに行く.商品の情報は 2 つの配列 profit, city で与えられ,i 番の商品は,街 city_i で売ることができて,そのときの利益が profit_i であることを表す.商品を売りに行く街の訪問順序は予め決まっている.その情報は配列 visit で与えられ,i 番目に訪問する街が visit_i である.また,ある商品は高々 1 回しか売ることはできず,ある街への 1 回の訪問では高々 1 つの商品しか売ることはできない.
 得られる利益の総和の最大値を求めよ.

解法

 商品を売れる街が決まっているので,売れる街が異なる商品については独立に考えることができます.
 ある街での判断について考えます.前提として,商品が残っているならば,売らないという選択は明らかに損です,そのことを踏まえると,街への訪問回数とその街で売れる商品の数の内で小さい方を m としたとき,そこで売れる商品の内,収入が大きいものから順に m 個の商品を売るのが最適な戦略となります.
 あとは,全ての街についてこの戦略をシミュレートして,利益の総和を計算すれば問題を解くことができます.

コード

using VI = vector< int >;
using VVI = vector< VI >;

#define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back

class TravellingSalesmanEasy
{
public:
	int getMaxProfit( int M, vector <int> profit, vector <int> city, vector <int> visit )
	{
		const int N = profit.size();

		{
			auto f = bind( minus< int >(), _1, 1 );
			transform( ALL( city ), city.begin(), f );
			transform( ALL( visit ), visit.begin(), f );
		}

		VVI profits( M );
		REP( i, N )
		{
			profits[ city[i] ].PB( profit[i] );
		}
		for_each( ALL( profits ), []( VI &v ){ sort( ALL( v ), greater< int >() ); } );

		VI counts( M );
		for_each( ALL( visit ), [&]( const int v ){ ++counts[v]; } );

		int res = 0;
		REP( v, M )
		{
			const int m = min( SZ( profits[v] ), counts[v] );
			res += accumulate( profits[v].begin(), profits[v].begin() + m, 0 );
		}
		return res;
	}
};