TopCoder SRM 579, Division 1, Level 2 : TravellingPurchasingMan

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=11050&rd=15499

概要

N 個の店があって、そのうち M 個の店に興味がある。
いくつかの店の間には道があり、その移動時間が与えられる。
また、興味がある店について、開店時刻・閉店時刻・買い物の所要時間の情報が与えられる。
時刻 0 で N - 1 番の店から買い物を始めるとき、買い物ができる興味のある店の数の最大数を求めよ。

解法

はじめに Warshall-Froyd で全点間の最小コストを求めておきます。

本題ですが、
dp[ 既に買い物をした店の集合 ][ 現在位置 ] := 最短の所要時間
として Bit DP です。
ただし、状態遷移をするときに注意する点が二つあって

• 開店時刻より早く買い物を始めることはできない
• 閉店時刻に間に合わない場合は遷移できない

これらの状態は弾く必要があります。

この DP が終了したあと、到達できた状態について「既に買い物をした店の集合」の要素数（立っている Bit の数）のうち、最大のものが答えです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef istringstream ISS;

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

const int INF = INT_MAX / 2;

class TravellingPurchasingMan
{
public:
	int maxStores(int N, vector <string> interestingStores, vector <string> roads)
	{
		VVI G( N, VI( N, INF ) );
		REP( i, 0, N )
		{
			G[i][i] = 0;
		}

		REP( i, 0, roads.size() )
		{
			ISS iss( roads[i] );
			int a, b, c;
			iss >> a >> b >> c;
			G[a][b] = G[b][a] = min( G[a][b], c );
		}

		REP( k, 0, N )
		{
			REP( i, 0, N )
			{
				REP( j, 0, N )
				{
					G[i][j] = min( G[i][j], G[i][k] + G[k][j] );
				}
			}
		}
		
		const int M = interestingStores.size();
		VI starts( M ), ends( M ), durations( M );
		REP( i, 0, M )
		{
			ISS iss ( interestingStores[i] );
			iss >> starts[i] >> ends[i] >> durations[i];
		}

		VVI dp( 1 << M, VI( M, INF ) );
		REP( i, 0, M )
		{
			if ( G[ N - 1 ][i] <= ends[i] )
			{
				dp[ 1 << i ][i] = max( starts[i], G[ N - 1 ][i] ) + durations[i];
			}
		}

		REP( mask, 0, 1 << M )
		{
			REP( i, 0, M )
			{
				REP( j, 0, M )
				{
					if ( dp[ mask ][i] + G[i][j] <= ends[j] )
					{
						dp[ mask | 1 << j ][j] = min( dp[ mask | 1 << j ][j], max( dp[ mask ][i] + G[i][j], starts[j] ) + durations[j] );
					}
				}
			}
		}

		int res = 0;
		REP( mask, 0, 1 << M )
		{
			REP( i, 0, M )
			{
				if ( dp[ mask ][i] < INF )
				{
					res = max( res, numBit( mask ) );
				}
			}
		}

		return res;
	}

	int numBit( int mask )
	{
		int res = 0;
		REP( i, 0, 20 )
		{
			res += mask & 1 << i ? 1 : 0;
		}
		return res;
	}
};