TopCoder SRM 581 Div1 Easy SurveillanceSystem

問題

n個の部屋が一直線上に並んでいる。
i個目の部屋にコンテナが置いてあるかどうかが与えられる。


部屋をいくつかの監視カメラが監視している。


全ての監視カメラは、長さLの連続する部屋を監視している。
それぞれの監視カメラが監視する部屋に重複があることがあるが、
二つの監視カメラの監視する部屋が全て同じであることはない。


それぞれの監視カメラが、監視している部屋に含まれているコンテナの数の合計が与えられる。
このとき、それぞれの部屋について、

  • 1台以上のカメラが監視していることが保証されている
  • 監視しているカメラが1台もないことが保証されている
  • わからない

のどれであるかを答えよ。
入力には矛盾はない。

制約条件

n≦50
L≦50
監視カメラの個数は1以上n - L + 1以下

方針

簡単な方法がわからなかったので、フローに流量制約をつけてといた。
カメラが部屋を監視している有効な組み合わせというのは、
カメラが監視できる全ての区間の候補n - L + 1個と、カメラのマッチングがあること。


部屋ごとに、カメラで見られるかそうでないかを求める。


ある部屋を監視カメラが必ず見る⇔その部屋を監視できないとき、大きさmのマッチングが存在しない。
ある部屋を監視カメラが絶対見ない⇔その部屋を監視したとき、大きさmのマッチングが存在しない


前者は、その部屋を見るための辺を削除して二部マッチングを求めればいい。
後者は、その部屋を見るための辺のどれかに最低流量1が流れるものとして二部マッチングを求めればよい。
これはどうするかというと、
部屋を含む区間をa, a + 1, ... a + kとすると、
頂点x, yを作って、x→yに流量1が流れることを保証し、
yからa, a + 1, ..., a + kに流量1の辺を張ればよい。


最低流量のあるフローについては詳しくは蟻本参照。
といってもx→yに1流さなければならないとき、
元の辺のかわりに、s→yに1, x→tに1の辺を張るだけ。

ソースコード

bool can(int pos, const string &in, vi r, int len, bool flag){
	vi l;
	rep(i, in.size() - len + 1){
		int cnt = 0;
		rep(j, len) cnt += in[i + j] == 'X';
		l.pb(cnt);
	}
	int n = l.size(), m = r.size();
	int s = n + m, t = n + m + 1, a = t + 1, b = t + 2;
	int S = a + 1, T = b + 2;
	
	flowGraph g(T + 1);
	rep(i, n) rep(j, m) if(l[i] == r[j]) g.add(i, j + n, 1);
	if(flag){
		rep(i, n){
			if(i <= pos && pos < i + len) continue;
			g.add(s, i, 1);
		}
		rep(i, m) g.add(i + n, t, 1);
		return g.max_flow(s, t) < m; //if not use, then impossible
	}
	//if use, then impossible
	g.add(S, s, m - 1); g.add(t, T, m - 1);
	g.add(S, b, 1); g.add(a, T, 1);
	rep(i, n){
		g.add(i <= pos && pos < i + len ? b : s, i, 1);
	}
	rep(i, m) g.add(i + n, T, 1);
	return g.max_flow(S, T) < m;
}

class SurveillanceSystem {
	public:
	string getContainerInfo(string containers, vector <int> reports, int L) {
		int n = containers.size();
		string ans;
		rep(i, n){
			if(can(i, containers, reports, L, 1)) ans += "+";
			else if(can(i, containers, reports, L, 0)) ans += "-";
			else ans += "?";
		}
		return ans;
	}
};