torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

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

問題概要

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

解法

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

コード O( N )

#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;
	}
};

コード O( N^3 )

#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;
	}
};