TopCoder SRM 581 Div1 Easy SurveillanceSystem

問題

長さnの部屋が一直線上に並んでいる。
containers[i]はi番目の部屋にコンテナが置いてあるとき'X'で、そうでないときは'-'である。
監視カメラがいくつかあり、一つの監視カメラは連続するL個の部屋を監視している。

それぞれの監視カメラに写っているコンテナの数が与えられる。
複数の監視カメラが同じ部屋の集合を監視していることはない。（一つの部屋を複数の監視カメラが監視することはありえる）

各部屋について、

• 一つ以上の監視カメラが監視していることが保証されている
• どの監視カメラも監視していないことが保証されている
• 上のどちらでもない

のどれであるかを出力せよ。

制約条件

n≦50
L≦n

方針

ソースコード

int n, m, L;
vi cnt, reports;

bool mustuse(int idx){
	
	int l = n - L + 1;
	int s = l + m, t = s + 1;
	
	flowGraph g(t + 1);
	
	rep(i, m){
		g.add(s, i, 1);
		rep(j, l) if(cnt[j] == reports[i]) g.add(i, j + m, 1);
	}
	rep(i, l){
		if(i <= idx && idx < i + L) continue;
		g.add(i + m, t, 1);
	}
	return g.max_flow(s, t) < m;
}
bool mustnotuse(int idx){
	
	int l = n - L + 1;
	int s = l + m, tt = s + 1, t = s + 2;
	
	flowGraph g(t + 1);
	
	rep(i, m){
		g.add(s, i, 1);
		rep(j, l) if(cnt[j] == reports[i]) g.add(i, j + m, 1);
	}
	rep(i, l){
		if(i <= idx && idx < i + L) g.add(i + m, t, 1);
		else g.add(i + m, tt, 1);
	}
	g.add(tt, t, m - 1);
	
	return g.max_flow(s, t) < m;
}

class SurveillanceSystem {
	public:
	string getContainerInfo(string containers, vector <int> reports, int L) {
		
		n = containers.size();
		m = reports.size();
		cnt.clear();
		::reports = reports;
		::L = L;
		string ans;
		
		rep(i, n - L + 1){
			int k = 0;
			rep(j, L) k += containers[i + j] == 'X';
			
			cnt.pb(k);
		}
		rep(i, n){
			if(mustuse(i)) ans.pb('+');
			else if(mustnotuse(i)) ans.pb('-');
			else ans.pb('?');
		}
		return ans;
	}
};