TopCoder SRM 727 Div1 Medium Subrectangle

なかなか面白い問題。
https://community.topcoder.com/stat?c=problem_statement&pm=14779

問題

各文字が白黒マスのいずれかを示す文字列が与えられたとする。

ここで、ある二次元グリッドを考える。
このグリッドは全体的に白で、一部矩形範囲が黒であるとする。
このグリッドの構成マスをrow-major-orderで並べ、いくつかのマスを取り除くと、入力の文字列になっていたとする。

入力の文字列を生成できる二次元グリッドを構築するために必要な最小取り除きマス数を求めよ。

解法

削除前のグリッドにおいて、黒マスが存在する行はXマス白マス、Yマス黒マス、Zマス白マス、の順で並んでいたと考える。
この(X,Y,Z)を総当たりしつつ、それを満たす場合に必要な追加マス数を求め、その最小値を求めればよい。

最初に入力文字列をランレングス圧縮しておくとよい。
入力文字列にXより多くの白マスがある場合、1行(X+Y+Z)列の白マスをいくつか並べなければならない。

その後、未処理の黒マスがある限り以下を続ける。

• Xより多くの白マスが連続するある場合、X個の白マスとY個の黒マスを追加し、最後のZ個の白マスに入力分を配置すると考えよう。
• 次に黒マスがY個以下連続するなら1行に(追加分含め)Y個並べればいいし、Y個より多いなら行を追加してY個ずつ黒マスを配置していけばよい。
• 各行の最後にZ個の白マスを配置する。

入力の黒マスがなくなってもまだ白マスが残っているなら、1行(X+Y+Z)列の白マスをいくつか並べなければならない。

(X,Y,Z)の総当たりを単純にO(N^3)かけて行うとTLEするので、白マス黒マス数を踏まえX,Y,Zの探索範囲を絞るとよい。

class Subrectangle {
	public:
	int minMissed(string S) {
		vector<pair<int,int>> V;
		V.push_back({0,0});
		FORR(c,S) {
			c=(c=='#');
			if(V.empty() || V.back().first!=c) V.push_back({c,1});
			else V.back().second++;
		}
		if(V.back().first==1) V.push_back({0,0});
		
		if(V.size()==1) return 1;
		if(V.size()==3) return 0;
		
		int A[2]={0,0};
		FORR(v,V) A[v.first]=max(A[v.first],v.second);
		
		
		
		int mi=1<<20;
		int x,y,z;
		FOR(x,301) FOR(y,A[1]+1) FOR(z,A[0]-x+1) if(y && x+y+z<mi) {
			int W=x+y+z;
			int H=0;
			deque<pair<int,int>> D;
			FORR(v,V) D.push_back(v);
			while(D.front().second>x) {
				H+=W;
				D.front().second-=W;
				if(D.front().second<0) D.front().second=0;
				if(H>=mi) break;
			}
			if(H>=mi) continue;
			while(D.size()>1) {
				H+=W;
				if(H>=mi) break;
				if(D.front().first==0 && D.front().second>x) {
					if(x+z==0) {
						H=mi+1;
						break;
					}
					D.front().second-=x+z;
					continue;
				}
				if(D.front().first<=0) D.pop_front();
				if(D.front().second>y) {
					D.front().second-=y;
					if(H>mi) break;
					continue;
				}
				D.pop_front();
				D.front().second-=z;
			}
			if(H>mi) continue;
			H+=(D.back().second+W-1)/W*W;
			mi=min(mi,H);
			
		}
		
		return mi-S.size();
		
	}
}

まとめ

こういう問題をコンスタントに出せればSRMもう少し盛り上がるんだろうにな。