torus711 のアレ

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

TopCoder SRM 613, Division 1, Level 1 ( Divisin 2, Level 2 ) : TaroFriends

問題概要

 いくつかの整数値が与えられる。これらの整数値全てに対し、絶対値が X であるような整数値を一度ずつ加算する。得られた整数値の最大値と最小値の差の最小値を求めよ。

解法

 解を決定付ける値は、操作後に於ける最小値と最大値の二つなので、二つの値の組み合わせとそれらに対する操作を全通り試すと考えます。着目した二つの値から得られる操作後の値を x1, x2 ( x1 <= x2 ) としたとき、適切な操作をすることで全ての値を [ x1, x2 ] の区間内に入れることが可能ならば、それらは妥当な最小・最大値です。x1, x2 が決まったとき、「ある値 c を [ x1, x2 ] 内に入れることができる」とは、「 c - X が区間内に入る または c + X が区間内に入る」と同値です。全ての値がこの条件を満たすような x1, x2 から得られる x2 - x1 の値の内、最小のものが問題の答えです。

コード

using VI = vector<int>; using VVI = vector<VI>;
template < typename T > 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()

const int INF = LIM<int>::max() / 2;

const int dx[] = { -1, 1 };

class TaroFriends
{
public:
	int getNumber( vector <int> coordinates, int X )
	{
		const int N = coordinates.size();
		if ( N == 1 )
		{
			return 0;
		}

		VI ps1, ps2;
		transform( ALL( coordinates ), back_inserter( ps1 ), bind( plus<int>(), placeholders::_1, X ) );
		transform( ALL( coordinates ), back_inserter( ps2 ), bind( minus<int>(), placeholders::_1, X ) );

		int res = INF;
		REP( i, 0, N )
		{
			REP( j, 0, i )
			{
				REP( s, 0, 1 << 2 )
				{
					int x1 = coordinates[i] + X * dx[ !!( s & 1 ) ];
					int x2 = coordinates[j] + X * dx[ !!( s & 2 ) ];
					if ( !( x1 <= x2 ) ) swap( x1, x2 );
					
					auto ok = [&]( const int x ){ return x1 <= x && x <= x2; };

					vector<bool> fs1, fs2;
					transform( ALL( ps1 ), back_inserter( fs1 ), ok );
					transform( ALL( ps2 ), back_inserter( fs2 ), ok );

					vector<bool> fs;
					transform( ALL( fs1 ), fs2.begin(), back_inserter( fs ), logical_or<bool>() );

					if ( all_of( ALL( fs ), []( const bool b ){ return b; } ) )
					{
						res = min( res, x2 - x1 );
					}
				}
			}
		}

		return res;
	}
};