AtCoder Regular Contest #022, B : 細長いお菓子

問題文

http://arc022.contest.atcoder.jp/tasks/arc022_2

問題概要

　N 項からなる数列 A が与えられる。A の連続する部分列であって部分列に含まれる要素が相異なるものの内、長さが最大のものの長さを求めよ。
　

解法

　N が大きいので、区間の両端を全て試すなどの方法はとれません。より効率的な方法を考えます。
　ある valid な部分列が存在して、そのすぐ右側の要素を部分列に加えても valid なとき、その要素は部分列に加えてしまった方が得で、ある左端を決めたとすれば、可能な限り右に伸ばすのが、その左端に対する最適となります。他方、ある valid な部分列の左端の要素を部分列から取り除いても、その部分列は valid なままです。また、部分列の左端を順に仮定して最大の長さを探すとすると、ある左端を仮定したときの valid な部分列が最長となる右端は、直前の左端によって得られた最大の右端と等しいか、より右側にあります。
　部分列が valid かどうかを求めるには、ある値が部分列に含まれるかどうかの boolean 配列をもっておくと、加えようとしている値が部分列に含まれるかどうかを定数時間で求められます。また、部分列から値を外す際も、該当する位置を false にすればよいので定数時間で更新できます。
　まとめると、左端を順に試しつつ、以前の結果を利用しながら最長の valid な部分列を与える右端を探すというアルゴリズムが考えられます。左端も右端も常に右方向に動き続けるので、インデックスの更新は 回しか発生せず、部分列の中身の管理は定数時間なので全体で 時間で動作します。

コード

using VI = vector<int>;
template < typename T = int > using VT = vector<T>;

#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

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

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}
	transform( ALL( as ), as.begin(), bind( minus<int>(), _1, 1 ) );

	int res = 0, t = 0;
	VT<bool> used( n );
	for ( int s = 0; s < n; used[ as[ s++ ] ] = false )
	{
		while ( t < n && !used[ as[t] ] )
		{
			used[ as[ t++ ] ] = true;
		}
		res = max( res, t - s );
	}

	cout << res << endl;

	return 0;
}