torus711 のアレ

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

Codeforces #243, Division 1, A ( Division 2, C ) : Sereja and Swaps

問題概要

 項数 n の数列 a と整数 k が与えられる。m( a ) を a の連続する部分列の和の最大値とし、a の二つの要素を交換する操作を最大 k 回できるとき、m( a ) の最大値はいくらか。
 なお、n \leq 200 である。

解法

 a の連続する部分列の個数は O( n^2 ) です。総和の最大値をとるある一つの部分列を仮定したときの最適なスワップ操作をある程度高速にシミュレートできれば問題を解けます。
 部分列を固定すると、a の要素は部分列に含まれるものとそうでないものに分かれます。このとき、意味のあるスワップ操作は部分列に含まれるものとそうでないものを交換する操作のみです。また、スワップの対象は、部分列に含まれるものからは値が小さいものを優先して、そうでないものからは値の大きいものを優先することで部分列の総和を最大化できます。要素の選択は、a の要素を予め分類した上でソートしておけば簡単にできるので、前処理に O( n \log n )スワップ操作群の適用は O( n ) になります。全体で O( n^3 \log n ) で、きつそうですが間に合います。

コード

using VI = vector<int>;

template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, K;
	cin >> n >> K;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int res = LIM<>::min();

	REP( i, 0, n )
	{
		REP( j, i, n )
		{
			VI inner, outer;

			REP( k, 0, n )
			{
				( i <= k && k <= j ? inner : outer ).PB( as[k] );
			}

			sort( ALL( inner ) );
			sort( ALL( outer ), greater<int>() );

			const int m = min<int>( { inner.size(), outer.size(), K } );
			REP( k, 0, m )
			{
				inner[k] = max( inner[k], outer[k] );
			}

			res = max( res, accumulate( ALL( inner ), 0 ) );
		}
	}

	cout << res << endl;

	return 0;
}