torus711 のアレ

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

AOJ 0517 : Longest Steps

解法

まず、各数字が存在するか否かを配列にします。
その配列から、存在しない数の個数が許容される範囲(空白カードがあれば 1 以下、無ければは 0 以下)に収まる区間をしゃくとり法で求め、最長のものを答えとします。

コード

typedef vector<int> VI;

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

int solve( VI cards )
{
	const int N = cards.size();
	int cap = cards[0];

	int s = 1, t = 1, numSpace = cards[1] == 0, res = 0;

	while ( s < N )
	{
		while ( t + 1 < N && numSpace <= cap )
		{
			numSpace += cards[ ++t ] == 0;
		}

		res = max( res, t - s );
		numSpace -= cards[ s++ ] == 0;
	}

	return res;
}

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

	while ( true )
	{
		int n, k;
		cin >> n >> k;

		if ( !( n | k ) )
		{
			break;
		}

		VI cards( 100001 );
		REP( i, 0, k )
		{
			int tmp;
			cin >> tmp;
			cards[ tmp ] = 1;
		}
		cout << solve( cards ) << endl;
	}

	return 0;
}