TopCoder, SRM 626, Division 2, Level 1 : SumOfPower

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13230&rd=15859

問題概要

　整数からなる列 が与えられる。 の全ての連続する部分列の総和を求めよ。

解法

　列の要素数を と書きます。また、添字は 0-based です。
　総和を計算するときに、 番目の要素が何回現れるかを知ることができれば、 に回数を書けて足し合わせることで総和を計算することができます。 番目の要素を含む連続する部分列の個数は、 のみを含む部分列をまず考えて、左右にそれぞれどれだけ伸ばせるか考えることで求めることができます。左には だけ伸ばすことができて、右には だけ伸ばすことができます。左右に伸ばす長さを独立に選べるので総数はこれらの積 です。これが が総和に出現する回数なので、全体では となり、これが答えです。このプログラムは に関する一重ループで書けるので で走ります。
　また、 が小さいことを考えると、部分列の端点を総当りして、その全てに対してループを回して総和を計算することもできます。こちらの解法ならば頭を使わずに書くことができます。部分列の総数が 、和の計算に かかるので、全体では かかります。

コード

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

class SumOfPower
{
public:
	int findSum( vector <int> array )
	{
		const int N = array.size();

		int res = 0;
		REP( i, 0, N )
		{
			res += array[i] * ( i + 1 ) * ( N - i );
		}
		return res;
	}
};

コード

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

class SumOfPower
{
public:
	int findSum( vector <int> array )
	{
		const int N = array.size();

		int res = 0;
		REP( i, 0, N )
		{
			REP( j, i, N )
			{
				REP( k, i, j + 1 )
				{
					res += array[k];
				}
			}
		}

		return res;
	}
};