torus711 のアレ

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

TopCoder, SRM 627, Division 2, Level 3 : BubbleSortWithReversals

問題概要

 整数列 A ( |A| \leq 50, \max( A ) \leq 1000 ) が与えられる。高々 K ( \leq 50 ) 個のオーバーラップしない A の連続する部分列を反転させる操作をした後、Aバブルソートで昇順ソートする。発生する交換操作の回数を最小化したときの、交換の回数を求めよ。

解法

 |A| = N, \max( A ) = M と書きます。
 まず、K=0 の場合について考えます。この場合、バブルソートの交換回数は A の転倒数と等しくなり、Fenwick Tree を用いることで O( N \log M ) 時間で求めることができます(蟻本参照)。
 上記のことを応用して K \neq 0 の場合について解きます。A の先頭から順に処理していくとして、反転させる区間がオーバーラップしないことを考えると、ある区間 [ l, r ) を反転させたとき、次に考慮する要素は r 番目の要素からで、インデックスの逆行は発生しません。このことを踏まえると次のように状態をとる動的計画法を考えることができます。

  • dp[ i 個考慮 ][ 反転の回数が j ] := 最小の交換回数(転倒数)

ある状態 dp[ i ][ j ] からは全ての状態遷移を試す必要があるので、

  • dp[ i + 1 ][ j ] を更新
  • dp[ k ][ j + 1 ] を更新(ただし ki < k \leq N なる全ての k

 更新時、転倒数の計算に時間をかけると危ないので Fenwick Tree を用いて高速化します。反転させない場合はそのまま転倒数を計算して、反転させる場合は( Fenwick Tree をコピーしてから)反転させる区間を逆順に Fenwick Tree で処理して転倒数を計算します。
 反転させない場合の計算量は O( \log M ) です。反転させる場合、一つの状態あたり k の値は O( N ) 種類の値をとり、一つの k について転倒数の計算に O( N \log M ) かかります。反転させない場合の計算量は反転させる場合のそれに比べて無視できるので消えて、一つの状態からの全ての遷移の計算にかかる時間は O( N^2 \log M ) です。全体の計算量はこれに状態数を掛けて O( N^3K \log M ) となります。

コード

using VI = vector<int>;
using VVI = vector<VI>;
template < typename T = int > using LIM = numeric_limits<T>;

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

constexpr int INF = LIM<>::max() / 2;

// Fenwick Tree ( Binary Indexed Tree )
class FenwickTree;
// FenwickTree( array size )
// int sum( 0-indexed pos )
// int add( 0-indexed pos, value )

class BubbleSortWithReversals
{
public:
	int getMinSwaps( vector <int> A, int K )
	{
		const int N = A.size();

		VVI dp( N + 1, VI( K + 2, INF ) );
		dp[0][0] = 0;

		FenwickTree bit( 1001 );
		REP( i, 0, N )
		{
			REP( j, 0, K + 1 )
			{
				{ // not reverse
					dp[ i + 1 ][j] = min( dp[ i + 1 ][j], dp[i][j] + bit.sum( 1000 ) - bit.sum( A[i] ) );
				}

				REP( k, i, N ) // reverse [ i, k ]
				{
					int d = 0;
					FenwickTree bit2 = bit;
					for ( int l = k; i <= l; --l )
					{
						d += bit2.sum( 1000 ) - bit2.sum( A[l] );
						bit2.add( A[l], 1 );
					}
					dp[ k + 1 ][ j + 1 ] = min( dp[ k + 1 ][ j + 1 ], dp[i][j] + d );
				}
			}

			bit.add( A[i], 1 );
		}

		return *min_element( dp.back().begin(), dp.back().end() - 1 );
	}
};