TopCoder SRM 538 Div2 Hard SkewedPerspectives

また文章で表現しづらい問題だ。
http://community.topcoder.com/stat?c=problem_statement&pm=11404

問題

問題文の図を見ることを推奨。

赤・青・黄色の正方形のブロックがいくつかと、高さが色つきブロックの倍ある黒いブロックがいくつか与えられる。
これらのブロックを幅Wブロック分の範囲で縦に積んで配置する。

クエリとして、左端からブロック群を見たときの色の見え方が与えられる。
そのような見え方をするブロック配置が可能か答えよ。

解法

左から見えたときのブロックを下から見ていき、それに応じて以下の手順で左端から積んでいく。

• 色つきブロックが見えるなら、今見ている段にそのブロックを積む。ただしそのブロックが足りなければ配置不可。
• 黒ブロックが高さ偶数個分見えるなら、今見ている段にその分黒ブロックを積む。ただし黒ブロックが足りなければ配置不可。
• 黒ブロックが高さが奇数個分見えるなら、今の段では配置不可能。よって次の段に今の段より1段低い分なんかしらのブロック(後で埋める)を積み、（黒ブロック高さ＋１）分黒ブロックを積む。黒ブロックが不足したり、幅がWをはみ出たら配置不可。

最後に、黒ブロック高さ奇数個分の処理で生じた、後で埋めないといけない高さを残りブロックで埋める。
色はなんでもよいので埋められたら配置可能。

class SkewedPerspectives {
	vector <int> C;
	int B,W;
	public:
	
	int okok(string req) {
		int CB=B;
		int h=0;
		int w=0;
		int i,x,y;
		vector<int> C2=C;
		vector<int> yo;
		
		FOR(i,req.size()) {
			if(req[i]!='b') {
				h++;
				if(C2[req[i]-'0']--==0) return 0;
			}
			else {
				int numb=0;
				while(i<req.size() && req[i]=='b') numb++,i++;
				i--;
				if(numb%2) {
					if(h==0) {
						if(numb==1) return 0;
						CB--;
						h=2;
						numb-=2;
					}
					yo.push_back(h-1);
					h+=numb;
					CB-=(1+numb)/2;
					if(CB<0) return 0;
					if(++w>=W) return 0;
				}
				else {
					h+=numb;
					CB-=numb/2;
					if(CB<0) return 0;
				}
			}
		}
		int NC=C2[0]+C2[1]+C2[2];
		FOR(i,yo.size()) {
			while(yo[i]>=2 && CB) CB--,yo[i]-=2;
			while(yo[i]>=1 && NC) NC--,yo[i]-=1;
			if(yo[i]) return 0;
		}
		return 1;
		
	}
	
	vector <string> areTheyPossible(vector <int> cubes, int B, int w, vector <string> views) {
		vector<string> R;
		int i;
		C=cubes;
		this->B=B;
		W=w;
		
		FOR(i,views.size()) {
			if(okok(views[i])) R.push_back("valid");
			else R.push_back("invalid");
		}
		return R;
	}
};

まとめ

SRMでこういうクエリ処理の問題って珍しいな。
ブロック群を横から見る問題はしばしば登場するね。