torus711 のアレ

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

TopCoder, Single Round Match 645, Division 2, Level 2 : ConnectingCars

問題概要

 直線状のレールの上に複数のカートが並んでいる.左から i 番目のカートの左端座標は position_i で,その長さは length_i である.
 このカートを,全て連結された状態にしたい.すなわち,position_i + length_i = position_i_{ i + 1 } のような状態にしたい.1 台のカートを距離 1 動かすためには 1 のコストがかかる.必要なコストの最小値を求めよ.
 |position| \leq 50
 position_i, length_i \leq 10^9

解法

 |position| = N と書きます.
 題意より,操作完了後には全てのカートが隣接している必要があるので,1 つのカートの位置を決めれば他のカートの位置も決まります.このとき,位置を固定したカート以外のカートについては,位置を固定したカートに向かって「寄せる」ことで最適な戦略をとることができます.しかし,座標の幅が大きいため,固定する位置を全通り試すことはできません.
 実は,ある最適な移動を完了した状態に於いて,少なくとも 1 つのカートの位置はその初期位置と一致しています.きちんとした証明ではありませんが,根拠的なものを書いてみます.全てのカートが初期位置から移動している状態を考えてみると,左端からある位置までの( 0 個以上の)連続したカートは全て右に移動していて,それ以外のカートは全て左に移動しています.このとき,台数の多い方の集団を元の位置に近づけるように全体をスライドさせると,(元の位置との差の絶対値をコストと考えれば)コストが減少します.それぞれの台数が同じ場合はコストは変化しないので,いずれかのカートが初期位置に到達するまで動かし続けることができます.従って,ある最適な状態に於いては,少なくとも 1 つのカートは初期位置と同じ位置にいることができます.
 このことを踏まえると,最初に述べた「 1 つのカートの位置を固定する」という処理は,「位置を固定するカートを 1 つ選ぶ」という処理になります.これは O( N ) 通りです.それぞれのパターンについて,固定したカートの隣のカートから順に「寄せて」いくようにシミュレートすると,そのときのコストの計算を O( N ) 時間で完了できます.従って,O( N^2 ) 時間で最適解を探すことができます.

コード

using LL = long long;
using PII = pair< int, int >;
using VPII = vector< PII >;
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() )
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

class ConnectingCars
{
public:
	long long minimizeCost( vector <int> positions, vector <int> lengths )
	{
		const int N = SZ( positions );

		VPII ps;
		transform( ALL( positions ), lengths.begin(), BI( ps ), []( const int a, const int b ){ return MP( a, b ); } );
		sort( ALL( ps ) );

		LL res = LIM< LL >::max();

		REP( c, 0, N )
		{
			LL tmp = 0;
			for ( LL i = c - 1, x = ps[c].fst; 0 <= i; --i )
			{
				tmp += x - ( ps[i].fst + ps[i].snd );
				x -= ps[i].snd;
			}
			for ( LL i = c + 1, x = ps[c].fst + ps[c].snd; i < N; ++i )
			{
				tmp += ps[i].fst - x;
				x += ps[i].snd;
			}

			res = min( res, tmp );
		}

		return res;
	}
};