TopCoder SRM 579 Div1 Medium TravellingPurchasingMan

久々の450pt Medium。ただ、submit者は多かったがパスした人は意外と少ないようだ。
うーん、アルゴリズムも完璧だったので、これを凡ミスしたのは勿体ない…。
http://community.topcoder.com/stat?c=problem_statement&pm=11050

問題

0～(N-1)番までのN個の店がある。そのうち自分が興味を持っているのは0～(M-1)番までのM(<=N)個の店である。
また、一部の店と店の間には双方向の道路があり、移動にかかる時間が与えられる。
さらに、M個の店に対し、開店時刻・閉店時刻・買い物にかかる時間が与えられる。
１つの店では１回までしか買い物できない。また、買い物の開始が閉店時刻前なら、買い物終了は閉店時刻を超えていても良い。

自分が最初(N-1)番の店の前にいるとき、買い物できる最大の店舗数を答える。

解法

気になるのが、N<=50の制約に対しM<=16であること。これを利用してBitDPすることを考える。
まず、N個の店の間の移動時間を全部求める。N<=50なのでFloyd法で良い。

ここから、買い物できる店の数を数えるわけだが、最初の一手で0～(M-1)の店に行ってしまえば、後はM～(N-1)番の店は用はない(移動で経由はするが、買い物はしない)。
よって、状態として[現在いる店の位置][購入済の店のビットマップ]ごとに到達可能な最短時刻を求めてDPすればよい。
到達時刻が閉店時刻前なら買い物が可能である。また、到達時刻が開店時刻前なら、開店時刻まで待って買い物ができる。
あとは到達できた状態のうち、購入済bitの数が一番多いものを答える。

計算量は[現在いる店の位置]×[次に行く店の位置]×[購入済の店のビットマップ]でO(M^2×2^M)。
これだと200ms程度で終了する。店の位置をM個でなくN個にするとTLEスレスレになるので注意。

ll cost[100][100];
ll minc[17][1<<17];

class TravellingPurchasingMan {
	public:
	
	vector<vector<int> > S;
	vector<vector<int> > R;
	vector<int> split_int(const string &str, char delim){
		vector<int> res;
		size_t current = 0, found;
		while((found = str.find_first_of(delim, current)) != string::npos){
			string s = string(str, current, found - current);
			res.push_back(atoi(s.c_str()));
			current = found + 1;
		}
		string s = string(str, current, str.size() - current);
		res.push_back(atoi(s.c_str()));
		return res;
	}
	
	inline int bitcount(unsigned int n) { return __builtin_popcount(n);}
	int maxStores(int N, vector <string> interestingStores, vector <string> roads) {
		int NS=interestingStores.size();
		int i,j,k;
		
		S.clear();
		FOR(i,NS) S.push_back(split_int(interestingStores[i],' '));
		FOR(i,N) {
			FOR(j,N) cost[i][j]=1LL<<50;
			cost[i][i]=0;
		}
		
		FOR(i,roads.size()) {
			vector<int> ss=split_int(roads[i],' ');
			cost[ss[0]][ss[1]]=cost[ss[1]][ss[0]]=ss[2];
		}
		FOR(i,N) FOR(j,N) FOR(k,N) cost[j][k] = min(cost[j][k], cost[j][i]+cost[i][k]);
		FOR(i,17) FOR(j,1<<17) minc[i][j]=(1LL<<50);
		FOR(i,NS) minc[i][0]=cost[i][N-1];
		
		int mask,cur,tar;
		int res=0;
		for(int mask=0;mask<(1<<NS);mask++) {
			FOR(cur,NS) {
				if(cost[cur][N-1]==(1LL<<50)) continue;
				if(minc[cur][mask]==(1LL<<50)) continue;
				res = max(res, __builtin_popcount(mask));
				
				FOR(tar,NS) {
					if(mask & (1<<tar)) continue;
					ll mi=max((ll)S[tar][0],minc[cur][mask] + cost[cur][tar]);
					if(mi<=S[tar][1]) minc[tar][mask | (1<<tar)] = min(minc[tar][mask | (1<<tar)] , mi+S[tar][2]);
				}
			}
		}
		
		return res;
	}
};

まとめ

本番は開店時刻の制約を間違えて「開店時刻前に着いたら買い物できない」として失敗。
なんとつまらないミス…と思ったら同じミスをした人もちょこちょこいたようだ。

文字列のparseを無駄に頑張ってるけど、１要素整数が３つとわかってるならsscanfすればいいのか…。