torus711 のアレ

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

TopCoder, Single Round Match 646, Division 1, Level 1 : TheConsecutiveIntegersDivOne

問題概要

 整数の集合があり,その要素は配列 numbers により与えられる.この集合に対し,ある 1 つの要素を選んでその値を 1 増やすまたは 1 減らす操作を任意回数できる.
 整数 k \leq |numbers| が与えられる.少なくとも k 個の連続する整数が集合に含まれるようにするために,必要な操作回数は最小で何回か?

解法

 |numbers| = N と書きます.
 まず k 個の要素の選び方について考えます.明らかに,より「近い」要素を選んだ方がよいので,最適な選び方では numbers を昇順に並べた列の,k 個の連続する要素を選んでいます.この時点で,k 個の要素の選び方は O( N ) 通りになります.あとは,選ばれた k 個の要素を連続する整数にするための操作回数を計算できれば,問題を解くことができます.
 この部分は大体 SRM 645, Division 2, Level 2 と同じ感じになります.選ばれた値たちの内,動かさないものを 1 つ決めると他の動かし方が決まるので,一番よいものを探します.最適な操作のうち 1 つは,1 つ以上動かない要素が存在します.

コード

using VI = vector< int >;
template < typename T = int > using LIM = numeric_limits< T >;

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

constexpr int INF = LIM<>::max();;

class TheConsecutiveIntegersDivOne
{
public:
	int find( vector <int> numbers, int k )
	{
		const int N = SZ( numbers );
		sort( ALL( numbers ) );

		int res = INF;
		REP( i, 0, N - k + 1 )
		{
			res = min( res, solve2( VI( numbers.begin() + i, numbers.begin() + i + k ) ) );
		}
		return res;
	}

	int solve2( const VI &as )
	{
		const int M = as.size();

		int res = INF;
		REP( c, 0, M )
		{
			int tmp = 0;
			for ( int i = c, t = as[c]; 0 <= i; --i, --t )
			{
				tmp += t - as[i];
			}
			for ( int i = c, t = as[c]; i < M; ++i, ++t )
			{
				tmp += as[i] - t;
			}
			res = min( res, tmp );
		}

		return res;
	}
};