torus711 のアレ

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

TopCoder, SRM 637, Division 2, Level 3 : ConnectingGameDiv2

問題概要

 グリッド状の盤面を使った 2 人ゲームをする。盤面上のセルは、いくつかの Region に分かれている。Region とは、盤面をグリッドグラフと見做したときに互いに連結であるセルの集合である。各グリッドがどの Region に属するかの情報は、文字列配列 baord によって与えられる。board 上で同じ文字が割り当てられたセル同士は、同じ Region に属する。
 ゲームは、2 ステップからなる。まず先攻のプレイヤーが、いくつかの Region を赤に塗る(選んだ Region 属するセルを全て赤に塗る)。次に、後攻のプレイヤーが、赤く塗られなかったセルを全て青に塗る。
 以上の操作が終わった後、盤面の一番上の行から一番下の行への青いパス(隣接する青いセル同士を繋げた列)が存在すれば、後攻のプレイヤーの勝ちとなる。
 先攻のプレイヤーが勝つために、塗らなければならないセルの数の最小値を求めよ。

解法

 達成したいものが最小カットに見えるので、まずは最小カットに帰着してみます。Region を頂点とするグラフを考えて、各頂点に容量を設定(頂点を入り口と出口に分けて、二点間を結ぶ辺にの容量を頂点にもたせたい容量とする)し、隣接する(辺を接する) Region 間に容量無限大の辺を張ります。更に、Source から一番上の行にあるセルを含む Region の入り口長点へ容量無限大の辺を張り、一番下の行にあるセルを含む Region の出口頂点から Sink へ容量無限大の辺を張ります。こうすると、このグラフの最小カット(=最大流)が問題の答えになります。
 ところで、拡張前のグラフは平面グラフです。平面グラフの最小カットは双対グラフの最短経路になるので、横方向の最短経路を求めることでも解くことができます。最小カットを考えたときに(拡張後のグラフで)カットされているのは(拡張前のグラフで言うと)頂点なので、辺に囲まれた領域間を頂点の容量を距離とする辺で結んだグラフを考えます。Region 間の辺の張り方は、点を共有する Region 同士に辺を張ります。更に、始点から一番左の列にあるセルを含む Region 、一番右の列にあるセルを含む Region から終点へそれぞれ長さ 0 の辺を張ります。経路の重みは Region に含まれるセルの数の合計とした場合の、このグラフ上での最短経路が、先程の最小カットに一致します。

コード

using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int,int>; using VPII = vector< pair<int,int> >;
template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )

#define EM emplace

#define fst first
#define snd second

#include <unordered_map>

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

class ConnectingGameDiv2
{
public:
	int getmin( vector <string> board )
	{
		const int H = board.size(), W = board[0].size();
		unordered_map< char, int > counts;

		FOR( row, board )
		{
			FOR( ch, row )
			{
				++counts[ ch ];
			}
		}

		VVI distance( H, VI( W, INF ) );
		priority_queue< PII, VPII, greater< PII > > que;
		REP( i, 0, H )
		{
			distance[i][0] = counts[ board[i][0] ];
			que.EM( distance[i][0], i * 100 );
		}

		while ( !que.empty() )
		{
			const int dist = que.top().fst;
			const int y = que.top().snd / 100;
			const int x = que.top().snd % 100;
			que.pop();

			if ( distance[y][x] < dist )
			{
				continue;
			}

			REP( dy, -1, 2 )
			{
				REP( dx, -1, 2 )
				{
					if ( !( dy | dx ) )
					{
						continue;
					}

					const int ny = y + dy;
					const int nx = x + dx;

					if (  0 <= ny && ny < H && 0 <= nx && nx < W )
					{
						const int d = board[y][x] == board[ ny ][ nx ] ? 0 : counts[ board[ ny ][ nx ] ];
						if ( distance[y][x] + d < distance[ ny ][ nx ] )
						{
							que.EM( distance[ ny ][ nx ] = distance[y][x] + d, ny * 100 + nx );
						}
					}
				}
			}
		}

		int res = INF;
		REP( i, 0, H )
		{
			res = min( res, distance[i][ W - 1 ] );
		}
		return res;
	}