TopCoderOpen 2015 Round1C Easy DevuAndPlantingTrees

難易度がEasy≒Medium≒Hardに感じた。
http://community.topcoder.com/stat?c=problem_statement&pm=13743

問題

2行N列のグリッドからなる庭がある。
あるところに木を植えると、辺または角を共有する隣接セルには（互いの成長を妨害しないよう）木を植えることができない。

現状の庭の状態が与えられる。
この庭に最大何マス木を植えられるか答えよ。

解法

木が上の行にあっても下の行にあっても、その列と左右の列に他の木を植えられないことに代わりはない。

よって初期状態で2行ある庭の状態を1行に圧縮する。
上下どちらかの行に木がある場合、その列は圧縮後も木があると判定する。

• 木が1個もない場合
  • 解は(N+1)/2個
• 木が1個以上ある場合
  • 連続した空きマスの数をランレングス圧縮の要領で配列Vに詰めていく。
  • 配列の最初と最後は、V[i]/2個木を追加できる。
  • それ以外は、(V[i]-1)/2個木を追加できる。

class DevuAndPlantingTrees {
	public:
	int maximumTreesDevuCanGrow(vector <string> garden) {
		int L=garden[0].size();
		vector<int> V(1,0);
		int ret=0;
		int x=0;
		
		
		FOR(x,L) {
			if(garden[0][x]=='*' || garden[1][x]=='*') V.push_back(0), ret++;
			else V.back()++;
		}
		
		if(V.size()==1) ret=(L+1)/2;
		else {
			FOR(x,V.size()) {
				if(x==0 || x==V.size()-1) ret += V[x]/2;
				else ret += (V[x]-1)/2;
			}
		}
		return ret;
	}
}

まとめ

木がないケースで1WAした…。