torus711 のアレ

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

AtCoder Beginner Contest 180, E : Traveling Salesman among Aerial Cities

問題概要

 3 次元空間 $\mathbb R^3$ 上に都市 $1$ から都市 $N$ の $N$ 個の都市がある.都市 $i$ の座標は $( X_i, Y_i, Z_i )$ で与えられる.
 都市 $i$ から都市 $j$ に移動するときにかかるコストは $| X_i - X_j | + | Y_i - Y_j | + \max( 0, Z_j - Z_i )$ である.
 都市 $1$ を出発して,すべての都市を 一度以上通って都市 $1$ に戻ってくるときに必要なコストの最小値を求めよ.

制約

  • $2 \leq N \leq 17$
  • $-10^6 \leq X_i, Y_i, Z_i 10^6$
  • 与えられる都市の座標は相異なる

解法

 距離関数が特殊な形をしていることと,各都市を「丁度一度」ではなく「一度以上」訪問できる点が,よくある TSP (Traveling Salesman Problem) とは異なります.ちょっと気にしてあげないといけないのは,同じ都市を何度も通るようなルートを考慮する必要性の有無です.距離を求める式を $| X_i - X_j | + | Y_i - Y_j |$ の部分(単なる Manhattan 距離)と $\max( 0, Z_j - Z_i )$ に分けてみると見通しがよいかと思いますが,この距離関数は三角不等式を満たします.すなわち,2 点間の距離を $d( *, * )$ で表すとすれば,空間上の 3 点 $a, b, c$ について,$d( a, b ) + d( b, c ) \geq d( a, c )$ が成り立ちます.つまり,ある点からある点に移動するとき,どこか遠回りをして得をすることはありません.結果として,各都市は丁度一度ずつ訪問するという制約でもよいことになり,通常の TSP と同じになります.
 通常の TSP に対しては,$O( 2^N N^2 )$ 時間で解くアルゴリズムが知られて [1] おり,今回もそのアルゴリズムで解くことができます.具体的には,都市の集合を $S$ で表すことにすると,

  • $dp[S][i] \overset{def}{ \Longleftrightarrow } $ $S$ に含まれる都市は訪問済みで,現在地は $i$ な状態に至る最小コスト

という DP をします.初期化は

  • $dp[ \emptyset ][0] = 0$
  • $dp[S][i] = \infty$

です.ここで各状態 $dp[S][i]$ からの遷移は,次に行く都市 $j$ をすべて試して,$dp[ S \cup \{ j \} ][j]$ を $dp[S][i] + d( i, j )$ との $\min$ で更新します.最後に $dp[S][0]$ を読むと答えが求まっています.
 配列添字としての集合をどう扱うかですが,集合はビット表現(=整数)としてエンコードできます.すなわち,

  • $i$ 番目の要素が集合に入っている $\Leftrightarrow$ 整数の $i$ 番目のビットが立っている

というような整数で集合を表すことができ,配列の添字に使えます.

参考文献

[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. "プログラミングコンテストチャレンジブック." (2010).

コード

constexpr auto INF = LIM< LL >::max() / 2;

int main()
{
	IN( int, N );
	VI X( N ), Y( N ), Z( N );
	REP( i, N )
	{
		cin >> X[i] >> Y[i] >> Z[i];
	}

	static LL dp[ 1 << 17 ][ 32 ];
	fill( AALL( dp ), INF );
	dp[0][0] = 0;
	REP( s, 1 << N )
	{
		REP( i, N )
		{
			REP( j, N )
			{
				const int d = abs( X[i] - X[j] ) + abs( Y[i] - Y[j] ) + max( 0, Z[j] - Z[i] );
				chmin( dp[ s | 1 << j ][j], dp[s][i] + d );
			}
		}
	}

	cout << dp[ ( 1 << N ) - 1 ][0] << endl;

	return 0;
}