torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 634, Division 2, Level 1 : MountainRanges

問題概要

 数列 Height が与えられる。Height の要素であって、その両隣の要素よりも真に大きいものの数を求めよ。

解法

 着目する要素を変えながら、条件を満たすものを数え上げることで解くことができます。予め先頭と末尾に 0 を挿入しておくと両端での処理が不要になります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

#define PB( n ) push_back( n )

class MountainRanges
{
public:
	int countPeaks( vector <int> heights )
	{
		heights.insert( heights.begin(), 0 );
		heights.PB( 0 );

		int res = 0;
		REP( i, 1, heights.size() - 1 )
		{
			res += heights[ i - 1 ] < heights[i] && heights[i] > heights[ i + 1 ];
		}
		return res;
	}
};