torus711 のアレ

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

TopCoder, Single Round Match 646, Division 2, Level 1 : TheConsecutiveIntegersDivTwo

問題概要

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

解法

 k = 1 のとき,1 つの整数は連続する k 個の整数と見做せるため,操作の必要はありません.この場合は 0 を return しておくとして,k = 2 の場合について考えます.
 まずは,ある 2 つの整数 a, b ( a < b ) をとったとき,a, b が連続する整数になる(⇔a + 1 = b)となるようにするための操作回数について考えてみます.この場合,b - a - 1 回の操作で目標を達成できます.nubmers から 1 つの要素を選んでそれを a として固定したと考えると,b の選び方として最適なものは,a より大きい要素の内最小のものを b とする選び方です.これは,予め numbers を昇順ソートしておくことで簡単に求めることができます.すなわち,ソート後の配列を numbers' として,各 i について numbers'_{ i + 1 } - numbers'_i - 1 を計算した内の最小値が答えとなります.

コード

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() )

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

		if ( k == 1 )
		{
			return 0;
		}

		sort( ALL( numbers ) );

		int res = LIM<>::max();
		REP( i, 0, N - 1 )
		{
			res = min( res, numbers[ i + 1 ] - numbers[i] - 1 );
		}
		return res;
	}
};