TopCoderOpen 2014 Round2B Easy SwitchingGame

TCO R2Bに参加。
Easyをそこそこの速度で解いたため、レートは微増。
でもいい加減Medium解かないとレート上がらないな…。
http://community.topcoder.com/stat?c=problem_statement&pm=13110

問題

M個の電球が並んでおり、初期状態は全てオフである。
ここで、N個のステージを順にクリアしたい。
各ステージの条件として、各電球の状態としてオン/オフ/どちらでも良いのいずれかが与えられる。

以下の処理を計何回行えば全ステージをクリアできるか、最小値を求めよ。

• 任意個の電球をオンにする。
• 任意個の電球をオフにする。
• クリア判定を行い、現在のステージの条件と電球の状態が一致すれば次のステージに進む。

解法

現在の電球の状態を持っておいて、順次ステージクリアをしていく。
今オンの電球があり、クリア条件がオフなら、そのステージで電球オフを行う必要がある。
逆に今オフの電球があり、クリア条件がオンなら、そのステージで電球オンを行う必要がある。

問題はクリア条件がどちらでも良い場合である。
これは可能なら先読みで電球をオン/オフすればよい。

すなわち、今のステージはどちらでも良くても、以後のステージでオン/オフにしておく必要があり、かつ今のステージで別の電球の都合でオン/オフできるなら、それに乗っかって一緒にオンオフすればよい。

class SwitchingGame {
	public:
	int N,M;
	int need[51][2];
	int fix[55][55];
	
	int timeToWin(vector <string> states) {
		N=states.size();
		M=states[0].size();
		ZERO(need);
		int i,x,y;
		int ret=N;
		
		FOR(y,N+1) FOR(x,M+1) fix[y][x]=N;
		for(y=N-1;y>=0;y--) {
			FOR(x,M) {
				if(states[y][x]=='?') fix[y][x]=fix[y+1][x];
				else fix[y][x]=y;
			}
		}
		
		string s="";
		FOR(i,M) s+="-";
		FOR(y,N) {
			int needp=0,needm=0;
			FOR(x,M) {
				if(s[x]=='-' && states[y][x]=='+') needp=1;
				if(s[x]=='+' && states[y][x]=='-') needm=1;
			}
			ret+=needp+needm;
			FOR(x,M) {
				if(states[y][x]!='?') s[x]=states[y][x];
				else {
					if(fix[y][x]<N && states[fix[y][x]][x]=='+' && needp) s[x]='+';
					if(fix[y][x]<N && states[fix[y][x]][x]=='-' && needm) s[x]='-';
				}
			}
		}
		return ret;
		
	}
}

まとめ

若干ややこしいとはいえ、350ptは盛りすぎのような。
それとも、想定がそもそもDiv1よりは難易度低めってこと？