torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

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