TopCoder SRM 581 Div1 Easy SurveillanceSystem

SRM581は不参加なので復習だけ。
幸いMediumも解けたのだが、EasyもMediumも１ミスしたので出なくて良かった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12588

問題

１次元に並んだマスのいくつかに箱があり、連続するLマスを監視するカメラがいくつか存在して箱を監視している。
箱の配置と、各カメラの監視範囲内に存在する箱の数が与えられたとき、各マスについて以下のいずれの状態かを文字列で答える。

• "+" : 必ず最低１個以上のカメラで監視される。
• "?" : カメラで監視される可能性がある
• "-" : カメラで監視されることはない。

解法

まず最初に、各マスから連続するLマスに、何個箱があるかを求めておこう。

最初、「各マスに対してカメラがあるかないか」でDFSしたら割とうまく行ったのだが、一部ケースでTLEしてしまった。
そこでもっと軽量な手法を考えた。

まず、「カメラで監視される可能性がある」のマスを求める。
上で各マスから連続するLマスにある箱の数を求めているので、同じ箱数を監視しているカメラが一つでもあれば、そこを監視するカメラが存在しうる。
よって、そのようなマスから連続するLマスはカメラで監視される可能性がある。

次に、「必ず最低１個以上のカメラで監視される」マスを求める。
以下の処理を各Mについて行う。

• M個の箱を監視するカメラがC個あったとする。
• 各マスについて、そこから連続するLマス中にM個箱がある場合、そこからLマスはカメラ監視の可能性がある。
• 上記の条件を満たすマスがP個ある場合、P-C+1個以上のカメラから監視される可能性があるなら、Pマス中どのCマスがカメラの監視の始点となっても１個以上のカメラに監視される。

マス目数Nに対して、O(N^2)で終わるので時間は余裕。
最初DFSをしたのはなんだったのだ…。

class SurveillanceSystem {
	int MM[101];
	set<ll> OK;
	int R,C;
	int N[50],NT[50];
	public:
	
	string getContainerInfo(string containers, vector <int> reports, int L) {
		int i,x,y,j;
		
		R=reports.size();
		C=containers.size();
		ZERO(MM);
		MM[100]=R;
		FOR(i,R) MM[reports[i]]++;
		
		ZERO(N);
		ll orm=0,andm=0;
		FOR(i,C-L+1) {
			FOR(j,L) if(containers[i+j]=='X') N[i]++;
			if(MM[N[i]]) orm |= ((1LL<<L)-1)<<i;
		}
		
		FOR(i,L+1) {
			if(MM[i]==0) continue;
			int num[51];
			int t=0;
			ZERO(num);
			FOR(x,C-L+1) if(N[x]==i) {
				FOR(y,L) num[x+y]++;
				t++;
			}
			
			FOR(x,C) if(num[x]>t-MM[i]) andm|=1LL<<x;
		}
		
		string res;
		FOR(i,C) {
			if(andm & (1LL<<i)) res+="+";
			else if(orm & (1LL<<i)) res+="?";
			else res+="-";
		}
		
		
		return res;
	}
}

まとめ

「N個からM個選ぶ」みたいなDFSは、N=50でもTLEすることがあるので注意だな。