TopCoder SRM 643 Div1 Medium TheKingsArmyDiv1

Resubmitが痛いが、凡ミスで落とさず済んだと考えるか。
http://community.topcoder.com/stat?c=problem_statement&pm=13526

問題

2行×N列のグリッドがある。
初期状態で各セルは'S'か'H'である。
このグリッドに対し、以下の何れかの処理を行える。

1. あるセルの内容を１つの隣接セルにコピーする。
2. ある列の内容を左右どちらかの隣列にコピーする。
3. ある行の連続したセルの内容を、もう一つの行にコピーする。

全セルを'H'にするのに必要な最小処理回数を求めよ。

解法

初期状態ですべて'S'の場合、'H'に出来ない。

実はこの問題１つ目の処理は使う必要はない。
各列の状態別に処理を行う。
列の内容がの場合、隣接したでない隣列の内容をコピーするためにコストを1払う。
(最低1つは'H'を含む列があるので、そこから順々にコピーすれば全てのをの何れかに出来る。
また、はそれ以上何もする必要なないので無視する。

このようにしてとの列を消すと、のようにHが１個だけの列が並ぶことになる。

ここからは３つ目の処理を行い上下方向のコピーを行う。
３つ目の処理では連続した列をまとめて処理できるので、同じ状態が連続した列は１つと考えてよい。
例えば上記の状態はとなる。
この状態において、残りの列の数Cが：

• C==0なら何もしない。
• Cが奇数なら、Hが少ない方の列にあるHを反対の行にコピーする。たとえば先の状態なら2・4列目を上から下にコピーして。後は片方の行が全部Hになるので、全体を反対の行にコピーする。この処理回数は(C+1)/2。
• Cが2以上の偶数なら、どちらかの行のHを１個ずつ反対の行に移してHだけの行を作り、最後にその行を反対行にコピーすればよいので、処理回数はC/2+1。

このように実はO(N)で解ける。

int N;
class TheKingsArmyDiv1 {
	public:
	int getNumber(vector <string> state) {
		N=state[0].size();
		if(count(state[0].begin(),state[0].end(),'H')+count(state[1].begin(),state[1].end(),'H')==0)
			return -1;
		vector<int> V;
		int i,x,ret=0;
		FOR(i,N) {
			int x=(state[0][i]=='H')*2+(state[1][i]=='H');
			if(x==0) ret++;
			else if(x==3) continue;
			else if(V.empty() || V.back()!=x) V.push_back(x);
		}
		
		if(V.size()%2==1) ret+=(V.size()+1)/2;
		else if(V.size()>0) ret+=V.size()/2+1;
		
		return ret;
	}
}

まとめ

文字で書くと長いけど、コード量は短いね。