TopCoder SRM 576, Division 2, Level 1 : TheExperimentDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12508&rd=15496

概要

N 個の蛇口が等間隔に並んでおり、その下に M 枚のスポンジを重ねて並べる。
一番上にあるスポンジは、その真上にある蛇口から落ちる水滴を吸収する。

蛇口から落ちる水滴の量と、スポンジの重なり方の情報が与えられる。
吸収する水滴の量を求めよ。

解法

「一番上になるスポンジがどれか」を示す長さ N の配列を用意しておいて、下のスポンジから順にそれがカバーする範囲をスポンジの番号で fill します。
すると、それぞれの蛇口の水滴がどのスポンジに当たるかが分かるようになるので、てきとーに結果を生成して終わりです。

コード

typedef vector<int> VI;

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

class TheExperimentDiv2
{
public:
	vector <int> determineHumidity( vector <int> intensity, int L, vector <int> leftEnd )
	{
		const int N = intensity.size(), M = leftEnd.size();

		VI upper( N, -1 );
		for ( int i = M - 1; 0 <= i; i-- )
		{
			fill( upper.begin() + leftEnd[i], upper.begin() + leftEnd[i] + L, i );
		}

		VI res( M, 0 );
		REP( i, 0, N )
		{
			if ( upper[i] == -1 )
			{
				continue;
			}
			res[ upper[i] ] += intensity[i];
		}
		return res;
	}
};