torus711 のアレ

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

Codeforces #223, Division 2, B : Sereja and Stairs

概要

 m 個の正整数がある。この正整数から幾つかを選んで並び替え、以下の制約を満たす数列 a を作りたい。

  • a_1 < a_2 < \cdots < a_{ i - 1 } < a_i > a_{ i + 1 } > \cdots > a_{ |a| - 1 } > a_{ |a| } を満たす i ( 0 \leq i < |a| ) が存在する

そのような列を一つ求め、その長さと内容を出力せよ。

解法

 位置 i を堺に手前が狭義単調増加、後ろが狭義単調減少になっています。i の制約から、後半(または前半)は無くても良いので、狭義単調増加(減少)な列は確実に作ることができます。与えられる数に重複が無ければこれで完了しています。重複がある場合、余った数を使って単調減少な列を作り後ろに繋げることで最も長い列を作ることができます。

コード

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 )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )

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

	int n;
	cin >> n;

	VI as( n );
	map<int,int> counts;
	FOR( a, as )
	{
		cin >> a;
		counts[a]++;
	}
	sort( ALL( as ) );

	for ( int i = n - 2; 0 <= i; i-- )
	{
		if ( 2 <= counts[ as[i] ] )
		{
			as.PB( as[i] );
		}
	}
	as.erase( unique( ALL( as ) ), as.end() );

	cout << as.size() << endl;
	REP( i, 0, as.size() )
	{
		cout << ( i ? " " : "" ) << as[i];
	}
	cout << endl;

	return 0;
}