面白いけどDiv2 Hardとしてはちょっと難易度低め。
http://community.topcoder.com/stat?c=problem_statement&pm=11844
問題
N人の人が円形に並んでいる。
各人が右隣の人のことを以下のいずれかと表現している、という状態が与えられる。
- 右隣の人は正直者である。
- 右隣の人は嘘つきである。
- 右隣の人はどちらかわからない。
各人が正直者と嘘つきのどちらであるか、矛盾のない組み合わせは存在するか。
また、その時あり得る嘘つきの最小人数は何人か。
解法
人が円形に並んでいるため、1人を正直/嘘つき決め打ちして右隣に順々に正直/嘘つきを割り当てていき、最後にまたN人目が最初の1人目を表現する際、最初の決め打ちと矛盾しないか判断すればよい。
その過程で、登場した嘘つきの最小回数を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; } }
まとめ
難易度は置いておいて、こういう問題作れるセンスはいいな。