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

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13625&rd=16278

問題概要

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

解法

　 と書きます．
　まず 個の要素の選び方について考えます．明らかに，より「近い」要素を選んだ方がよいので，最適な選び方では を昇順に並べた列の， 個の連続する要素を選んでいます．この時点で， 個の要素の選び方は 通りになります．あとは，選ばれた 個の要素を連続する整数にするための操作回数を計算できれば，問題を解くことができます．
　この部分は大体 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;
	}
};