TopCoder SRM 443 Div1 Medium

問題

最初A個の0とB個の1が並んでいる。
この中から、異なるちょうどK個の数字を自由に選び、0と1を反転させる操作を行うことができる。

最短でこの操作を何回行えば全ての数字を1にすることが出来るか、求めよ。
操作をどのように行っても1にすることができないとき、-1を返せ。

制約条件

A, B, K≦100000

方針

愚直にBFSするとO( (A + B) * K)時間くらいかかってTLE.
ノードの数は少ないのに、一度訪れたノードへの枝を何回も見てしまうから時間がかかる。

したがって、一度も訪れてないノードをsetに入れて、
一度しか見ないようにしてやる。

すると、O( (A + B) log(A + B) )時間くらいでBFSが出来て通る。

ソースコード

void push(set<int> &s, queue<pi> &q, int lo, int hi, int cost){
	
	set<int>::iterator it = s.lower_bound(lo);
	set<int> del;
	for(; it != s.end() && *it <= hi; it++){
		q.push(mp(*it, cost));
		del.insert(*it);
	}
	each(i, del) s.erase(*i);
}

class BinaryFlips {
  public:
  int minimalMoves(int A, int B, int K) {
		set<int> odd, even;
		int n = A + B;
		
		rep(i, n + 1){
			if(i % 2) odd.insert(i);
			else even.insert(i);
		}
		queue<pair<int, int> > q;
		q.push(mp(A, 0));
		
		while(!q.empty()){
			int a = q.front().first, cost = q.front().second;
			q.pop();
			
			if(a == 0) return cost;
			
			int b = n - a;
			int hi = a + K - 2 * max(0, K - b);
			int lo = a + K - 2 * min(a, K);
			
			if(lo % 2) push(odd, q, lo, hi, cost + 1);
			else push(even, q, lo, hi, cost + 1);
		}
		return -1;
  }
};