torus711 のアレ

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

AtCoder Regular Contest #017, B : 解像度が低い。

問題概要

 長さ N の整数の列が与えられる。この列の長さ K の連続する部分列であって、狭義単調増加なものの数を求めよ。

解法

 部分列を全て試すと、判定を含めて O( N^3 ) になって間に合わないので、より効率的な方法を考える必要があります。そこで、複数の部分列をまとめて数え上げる方法を考えます。
 例えば、K 以上の長さ L をもつ単調増加な部分列があったとすると、始点の選び方が L - K + 1 通りあるので、この長さ L の部分から L - K + 1 個の部分列を取り出すことができます。このときの L は、極大なものについてだけ考えると重複なく取り出すことができます。「どこまで見たか」を覚えておくことで、長さ L の区間の列挙は O( N ) でできます。長さ L の区間から取り出す長さ K の区間の数は定数時間で計算できるので、全体を O(N) で計算することができます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

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

	int n, k;
	cin >> n >> k;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	int res = 0, prev = 0;
	REP( i, 1, n )
	{
		if ( as[ i - 1 ] >= as[i] )
		{
			res += max( 0, i - prev - k + 1 );
			prev = i;
		}
	}
	res += max( 0, n - prev - k + 1 );
	
	cout << res << endl;

	return 0;
}