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

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13548&rd=16084

問題概要

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

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

　二人が共に T シャツを購入する日数を求めよ．
　

解法

　二人の行動は独立なので，それぞれ別にシミュレートすることができます．片方のキャラクターの行動のシミュレートは，キャラクターの所持金を更新するパートと， との大小比較を行って，条件を満たしていれば T シャツを購入するパートからなります．
　シミュレートにより，Quimey が 日目に T シャツを購入する場合に限り ，そうでなければ となるような配列 および，Peblo が 日目に T シャツを購入する場合に限り となる配列 を作ったとすると，問題の答えは です．これは要するにベクトルの内積なので，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;
	}
};