TopCoder SRM 625 Div2 Hard ConundrumReloaded

面白いけどDiv2 Hardとしてはちょっと難易度低め。
http://community.topcoder.com/stat?c=problem_statement&pm=11844

問題

N人の人が円形に並んでいる。
各人が右隣の人のことを以下のいずれかと表現している、という状態が与えられる。

• 右隣の人は正直者である。
• 右隣の人は嘘つきである。
• 右隣の人はどちらかわからない。

各人が正直者と嘘つきのどちらであるか、矛盾のない組み合わせは存在するか。
また、その時あり得る嘘つきの最小人数は何人か。

解法

人が円形に並んでいるため、１人を正直/嘘つき決め打ちして右隣に順々に正直/嘘つきを割り当てていき、最後にまたN人目が最初の１人目を表現する際、最初の決め打ちと矛盾しないか判断すればよい。
その過程で、登場した嘘つきの最小回数をDPで求めていけばよい。

O(N)と計算量は非常に小さい問題。

class ConundrumReloaded {
	public:
	int dp[52][2];
	int minimumLiars(string answers) {
		int N=answers.size();
		int fa,i,x,y,ma=100;
		
		FOR(fa,2) {
			FOR(x,N+1) dp[x][0]=dp[x][1]=100;
			dp[0][fa]=0;
			FOR(i,N) {
				if(answers[i]=='L' || answers[i]=='?') {
					dp[i+1][1]=min(dp[i+1][1],dp[i][0]+1);
					dp[i+1][0]=min(dp[i+1][0],dp[i][1]);
				}
				if(answers[i]=='H' || answers[i]=='?') {
					dp[i+1][1]=min(dp[i+1][1],dp[i][1]+1);
					dp[i+1][0]=min(dp[i+1][0],dp[i][0]);
				}
			}
			ma=min(ma,dp[N][fa]);
		}
		if(ma>=100) return -1;
		return ma;
	}
}

まとめ

難易度は置いておいて、こういう問題作れるセンスはいいな。