torus711 のアレ

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

TopCoder SRM 583, Division 1, Level 2 : TurnOnLamps

概要

N 頂点からなる木があり、木の各辺には 0 か 1 が割り当てられている。
この木に対して、二頂点を結ぶパス(一意に定まる)上の辺の数字を入れ替える操作ができる。
いくつかある "重要な辺" を全て 1 にするために必要な操作回数の最小値を求めよ。

解法

各段階で、"重要な辺" かつ 0 になっている辺を最も減らせるように二頂点を選ぶ Greedy で解けます。
未証明で出して未だに証明できていないのでコードだけ。

実装について書いておくと、大きく二つのパートに分けられます。
前半は、ある頂点から別のある頂点へ移動するときの経由辺を列挙しています。
始点の決め方を全通り試して、最短経路問題の経路復元のような感じでやりました。
後半部分が上で書いた Greedy の部分です。
各段階に於いてパスの端点の選び方を全通り試し、"重要な辺" かつ OFF になっている辺の数を最小化する選び方を採用していきます。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define PB( n ) push_back( n )

class TurnOnLamps
{
public:
	int minimize( vector <int> roads, string initState, string isImportant )
	{
		const int N = roads.size() + 1;

		vector<VVI> via_edges( N, VVI( N, VI() ) );
		{
			REP( s, 0, N )
			{
				queue<int> que;
				que.push( s );

				VI done( N, 0 ), prevv( N ), preve( N );
				done[s] = 1;

				while ( !que.empty() )
				{
					int cur = que.front();
					que.pop();

					REP( i, 0, N - 1 )
					{
						if ( i + 1 == cur && !done[ roads[i] ] )
						{
							prevv[ roads[i] ] = cur;
							preve[ roads[i] ] = i;
							que.push( roads[i] );
							done[ roads[i] ] = 1;
						}
						if ( roads[i] == cur && !done[ i + 1 ] )
						{
							prevv[ i + 1 ] = cur;
							preve[ i + 1 ] = i;
							que.push( i + 1 );
							done[ i + 1 ] = 1;
						}
					}
				}

				REP( g, 0, N )
				{
					for ( int v = g; v != s; v = prevv[v] )
					{
						via_edges[s][g].PB( preve[v] );
					}
				}
			}

			int res = 0;
			string state = initState;
			while ( true )
			{
				{ // check end?
					int rest = 0;
					REP( i, 0, N - 1 )
					{
						rest += isImportant[i] == '1' && state[i] == '0';
					}
					if ( rest == 0 )
					{
						return res;
					}
				}

				int u, v, best = 0;
				REP( i, 0, N )
				{
					REP( j, 0, N )
					{
						const VI &edges = via_edges[i][j];

						int tmp = 0;
						REP( k, 0, edges.size() )
						{
							tmp += isImportant[ edges[k] ] == '1' && state[ edges[k] ] == '0';
							tmp -= isImportant[ edges[k] ] == '1' && state[ edges[k] ] == '1';
						}

						if ( best < tmp )
						{
							u = i;
							v = j;
							best = tmp;
						}
					}
				}

				const VI &edges = via_edges[u][v];
				REP( i, 0, edges.size() )
				{
					state[ edges[i] ] = state[ edges[i] ] == '0' ? '1' : '0';
				}

				res++;
			}				
		}

		return -1;
	}
};