Codeforces 323, Division 1, B ( Division 2, D ) : Once Again...

問題文

　http://codeforces.com/contest/583/problem/D

問題概要

　$n$ 項の数列を $T$ 回繰り返した，$nT$ 要素の数列 $a$ が与えられる（与えられるのは最初の $n$ 要素のみ）．$a$ の単調非減少な部分列の内，最長のものの長さを求めよ．

• $1 \leq n \leq 100$
• $1 \leq T \leq 10^7$
• $1 \leq a_i \leq 300$

解法

　$\max\{ a \} = M $ とします．また，求めたいものは広義単調増加な列なので LIS と呼ぶことにします．

　まず，$a_i$ の範囲が小さく，LIS 中で隣接する 2 要素が異なる箇所は高々 300 箇所しかないことが分かります．従って，$a$ がとても長くなったとしても，LIS の殆どの部分では同じ値が並んでいることになります．長さ $n$ 毎に区切って考えると，殆どのセグメントからは同じ値を取り出しているということです．従って，この値が変わる部分だけ計算して，残りはてきとーに埋めると答えが分かります．

　$a$ を長さ $n$ 毎に区切って考えて，区切ったセグメント中で値が変わる部分に着目します．この着目部分の最適は，高々 300 個決めればよいのでがんばれば短時間で求められます．次のような DP をします．

• dp[ 列の末尾 ][ 使ったセグメントの個数 ] := 長さの最大

1 次元目は座標圧縮すれば幅が小さくなります．
　dp[ i ][ j ] からの遷移は，次の末尾を全て試すことになるので，

• dp[ k ][ j + 1 ] を dp[ i ][ j ] + ( $n$ 項から，i 以上 k 以下の要素だけで作る LIS の長さ ) で更新

となります．値の幅を決めたときの LIS は通常の LIS 同様に $O( \log n )$ 時間で求められます（蟻本参照）．幅の上下の取り方 $O( M^2 )$ 通りに対して前計算しておけば大丈夫です．加えて

• dp[ i + 1 ][ j ] を dp[ i ][ j ] で更新

もしておくと集計のときに楽になります．
　DP が終わったあと，各 j について，dp[ M ][ j ] + ( T - j ) * ( $n$ 要素から同じ数を選んで並べるときの個数の最大 ) を計算して，それらの内の最大値が答えです．ここで，( T - j ) というのは未使用のセグメントの数です．同じ数を並べる個数の最大は，$n$ 項に最も多く含まれる値の個数です．並べる数をどのように選んだとしても，適当な場所に挿入できるので，これで大丈夫です．

　この解法は，まず前計算に $O( M^2 \log n )$ 時間かかります．DP の状態数は $O( M^2 )$ で更新は $O( M )$ 通りなので DP 部分は $O( M^3 )$ 時間となります．よって，全体では $O( M^3 )$ 時間です．

コード

（ラスト数分のところで焦って書いたコードなのでちょっとおかしな所あります）

using VI = vector< int >;
using VVI = vector< vector< int > >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) begin( c ), end( c )

#define SZ( v ) ( (int)( v ).size() )

#define snd second

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

int solve2( const VI &A, const int lb, const int ub )
{
	const int N = SZ( A );
	VI dp( N + 1, INF );

	FOR( a, A )
	{
		if ( !( lb <= a && a < ub ) )
		{
			continue;
		}

		dp[ upper_bound( ALL( dp ), a ) - begin( dp ) ] = a;
	}
	return lower_bound( ALL( dp ), INF ) - begin( dp );
}

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

	int N, T;
	cin >> N >> T;

	VI A( N );
	cin >> A;

	VI nums( A );
	sort( ALL( nums ) );
	nums.erase( unique( ALL( nums ) ), end( nums ) );

	const int M = SZ( nums );
	VVI longest( M, VI( M ) );
	REP( i, M )
	{
		REP( j, i + 1, M )
		{
			longest[i][j] = solve2( A, nums[i], nums[j] + 1 );
		}
	}


	VVI dp( M + 1, VI( M + 1, -INF ) );
	dp[0][0] = 0;
	// dp[ 考慮数 ][ 使った数 ]

	REP( i, M )
	{
		REP( j, M )
		{
			REP( k, i, M )
			{
				dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] );
				dp[k][ j + 1 ] = max( dp[k][ j + 1 ], dp[i][j] + longest[i][k] );
			}
		}
	}

	map< int, int > counts;
	FOR( a, A )
	{
		++counts[a];
	}

	int ma = 0;
	FOR( a, counts )
	{
		ma = max( ma, a.snd );
	}

	int res = 0;
	REP( j, M )
	{
		res = max( res, dp[M][j] + ( T - j ) * ma );
	}
	cout << res << endl;

	return 0;
}