torus711 のアレ

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

ACL Contest 1, C : Moving Pieces

問題概要

 $N$ 行 $M $ 列のグリッド状の盤面がある.各セルは,

  • 何もない(空きである)
  • 障害物がある
  • 1 つの駒が置かれている

のいずれかである.
 ここで,次の操作が可能である.

  • 駒を 1 つ選び,右隣か下隣の空きセルに移動させる

最大で何回操作できるか?

制約

  • $1 \leq N, M, \leq 50$
  • 駒の個数は $100$ 以下

解法

 操作が終わった後の状態を想像してみます.すると,各駒は,その初期状態から到達できるいずれかのセルに移動していて,かつ,駒同士は位置を共有していないという状態になっているはずです.逆に,各駒に対してその最終位置を異なる駒同士では相異なるように決めてあげれば最終状態がひとつ定まります.また,適当な操作順序で操作すればそれは実現可能です.
 よって,問題は,各駒に対して,その最終位置を割り当てる問題であると言い換えることができます.また,各割当について,その駒で稼げる操作回数が benefit になります.こう言い換えただけだと解けませんが,次のようなグラフで最小費用流を流すと,コストの negate が答えになります.

  • 頂点集合は次の 4 つの union
    • 各駒
    • 各(最終状態での)位置
    • source
    • sink
  • 次のように辺を張る
    • source から各駒の入り口へ,流量 $1$ ,コスト $0$ の辺
    • 各駒から sink へ,流量 $1$ ,コスト $0$ の辺
    • 各駒から各最終位置へ,流量 $!$ ,コストをそのときの操作回数の negate とした辺

このグラフ上で source から sink への負コストを含む最小費用流を処理できれば,問題を解けます.

コード

// 最小費用流 O( F |E| log |V| )
#include <climits>
class MinimumCostFlow;
// MinimumCostFlow( |V| )
// connect( from, to, cap, cost )
// solve( s, t, f ) :  Primal-Dual O( F |E| log |V| )
// solve2( s, t, f ) : Bellman-Ford O( F |E| |V| )

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

VVI solve_one( const VS &board, const int y, const int x )
{
	const int H = SZ( board ), W = SZ( board[0] );

	VVI res( H, VI( W, -INF ) );
	res[y][x] = 0;

	REP( i, H )
	{
		REP( j, W )
		{
			if ( res[i][j] == -INF )
			{
				continue;
			}

			if ( i + 1 < H && board[ i + 1 ][j] != '#' )
			{
				chmax( res[ i + 1 ][j], res[i][j] + 1 );
			}
			if ( j + 1 < W && board[i][ j + 1 ] != '#' )
			{
				chmax( res[i][ j + 1 ], res[i][j] + 1 );
			}
		}
	}

	return res;
}

int main()
{
	IN( int, H, W );
	VS board( H );
	cin >> board;

	MinimumCostFlow mcflow( H * W * 2 + 2 );
	// [ 0, H * W ) := start positions
	// [ H * W, H * W * 2 ) := end positions
	const int SRC = H * W * 2;
	const int SINK = SRC + 1;

	const auto index = [&]( const int y, const int x )
	{
		return y * W + x;
	};

	int pieces = 0;
	REP( i, H )
	{
		REP( j, W )
		{
			if ( board[i][j] != '#' )
			{
				mcflow.connect( SRC, index( i, j ), 1, 0 );
				mcflow.connect( H * W + index( i, j ), SINK, 1, 0 );
			}

			if ( board[i][j] != 'o' )
			{
				continue;
			}

			++pieces;
			const auto distances = solve_one( board, i, j );
			REP( y, i, H )
			{
				REP( x, j, W )
				{
					if ( distances[y][x] != -INF )
					{
						mcflow.connect( index( i, j ), H * W + index( y, x ), 1, -distances[y][x] );
					}
				}
			}
		}
	}

	cout << -mcflow.solve( SRC, SINK, pieces ) << endl;

	return 0;
}