torus711 のアレ

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

TopCoder, Single Round Match 641, Division 2, Level 1 : BuyingTshirts

問題概要

 Quimey と Pablo は,これから N 日間に渡って T シャツを購入する.i 日目は,以下のように進行する.

  1. Quimey が Q_i ,Peblo が P_i の収入を得る
  2. Quimey と Peblo はそれぞれ,T 以上のお金を持っているときに値段 T の T シャツを一枚購入する.

 二人が共に T シャツを購入する日数を求めよ.
 Q_i, P_i \leq T

解法

 二人の行動は独立なので,それぞれ別にシミュレートすることができます.片方のキャラクターの行動のシミュレートは,キャラクターの所持金を更新するパートと,T との大小比較を行って,条件を満たしていれば T シャツを購入するパートからなります.
 シミュレートにより,Quimey が i 日目に T シャツを購入する場合に限り a_i = 1 ,そうでなければ a_i = 0 となるような配列 a および,Peblo が i 日目に T シャツを購入する場合に限り b_i = 1 となる配列 b を作ったとすると,問題の答えは \sum( a_i \times b_i) です.これは要するにベクトルの内積なので,std::inner_product を利用できます.

コード

using VI = vector< int >; using VVI = vector< VI >;
template < typename T = int > using VT = vector<T>; template < typename T = int > using VVT = VT< VT<T> >;

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

class BuyingTshirts
{
public:
	int meet( int T, vector <int> Q, vector <int> P )
	{
		VT< bool > q = solve( T, Q ), p = solve( T, P );
		return inner_product( ALL( q ), p.begin(), 0 );
	}

	VT< bool > solve( const int T, const VI &as )
	{
		const int N = as.size();

		int cur = 0;
		VT< bool > res( N );
		REP( i, 0, N )
		{
			cur += as[i];
			if ( T <= cur )
			{
				res[i] = true;
				cur -= T;
			}
		}
		return res;
	}
};