2013 TCO Algorithm - Round 1C, Level 1 : TheArray

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12455&rd=15585

概要

ある数列について、その項数、隣り合う要素の差の最大値、初項、末項が分かっている。
条件を満たす数列中のいずれかの要素が取りうる値の最大値を求めよ。

解法

求める数列は山形になります。
直接的に求めると面倒なので、やり方を工夫します。
前後から交差 d の増加列を作り、インデックス毎に小さい方をとったものの最大値が答えです。

コード

typedef vector<int> VI;

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

class TheArray
{
public:
	int find( int n, int d, int first, int last )
	{
		VI ary1( n ), ary2( n );

		REP( i, 0, n )
		{
			ary1[i] = first + i * d;
			ary2[ n - 1 - i ] = last + i * d;
		}
		
		int res = INT_MIN;
		REP( i, 0, n )
		{
			res = max( res, min( ary1[i], ary2[i] ) );
		}
		return res;
	}
};