世界中二人しか解けなかった問題、動的計画法

最近トップコーダーの問題を考えながら悩んでいます。正解のソースを見ても分からないところが多いです。
The problem appears to be a straightforward combinatorial search. Given a string of 0's and 1's in which some elements are replaced by question marks, the objective is to find the number of ways to replace the question marks such that the numer of 1's will be greater than or equal to K at time T. A further twist is given by the fact that the string is the state of a cellular automaton and that the characters at a given position change from time t to time t+1 based on the neighboring characters.
Assuming that there is no time element to the problem, the answer is simply, for Q question marks, N ones in string:
Sum(j=max(0,N-K) to Q)(choose(Q j))
This can be computed in O(Q*Q).
Given the time factor, though, this computation is insufficient. The rules for the evolution of the string are:
1. consider the ith element and its left and right neighbors (wrapping around the ends of the string if necessary)
2. If 2 or more of the three elements i-1 (mod len), i, i+1(mod N) are 1, ith is 1 at time t+1
3. else, ith element will be 0
A brute force approach to enumerating all possible assignments is as follows:
1. list all possible binary strings assigning values to '?'s.
2. For each such string, simulate the evolution of the original string with ? replaced by a value.
3. If, at time T, the number of 1's is greater than or equal to K, count this assignment.
This solution is O*1&&(i

*1:2^50)*T), though, which is unacceptable. The assumptions behind the given solution are (正解が前提にしている状況): 1. two consecutive bits that are the same will remain the same ad infinitum. 2. if the entire string consists of alternating bits and is of an even length, the bits will flip with each time step, but the number of ones will remain constant (例えば１０１０) Consider two bits of the same value which frame a sequence of alternating bits of odd length, e.g. 110101. Then: 1. Two ones which frame a 101... sequence will result in an increase of one 1 in each time step, and, at time T, the number of ones will be max(n+T,len) where len is the length of the sequence and n is number of 1s originally 2. Two zeroes framing a 010.. sequence will result in one 1 lost in each time step. After T steps the number of ones will be max(0,n-T). Additionally, a one and zero framing alternating bits of even length, like 110100. Then the result will be that the string will be partitioned with all 1s on one side and all zeroes on the other, but the number of ones will not change. This should account for all possible substrings formed within the initial string by replacing ? with 1 or 0. The question, though, is how does this alleviate the solution to the problem of enumerating 2^50 binary strings in order to count the number of strings which will result in an outcome with more than K ones. The solution suggests dynamic programming where, for a given start k and bit b1, dp[p][b2][ones] stores the number of substrings from k to p-1 such that bit b2 is at p and there are ones 1's. The complexity of enumerating all such values is 50*2*50 = 5000 for each start,bit pair. Times another 100 for the number of (start,bit) pairs results in O(500000) to traverse the data structure. If such a substring is of length N (length of init) and it contains K or more ones, the dp[p][b2][ones] value should be added to the final total. However, what if these strings were counted when considering a different startpoint and start bit? There must be a way to ensure that strings are not double-counted. It seems that only cases where the first bit equals the last bit (i.e. Nth bit) are considered. What if the start and end are different? It seems that this case would be subsumed in a different start position. If there is no start position such that init[(start+N-1)%N]=init[start], then the string is an alternating 1010... type of even length, which is handled by special conditional logic. The point then is to count all such n-tuples. What if there are no question marks, and what is the point of using different start points, if the bits for the start point are not ? ?. For a string with no ? characters, the answer should be either 0 or 1, depending on the number of 1s in init, it seems. This would also depend on the patterns discussed above. Also, though, if the string is something like 11111, then the results for every (start,bit) pair will be identical, and only one result (i.e. only one such N-tuple) should be counted. The point of the (start,bit) pair loop is that (start,bit) pairs with dp values greater than 0 represent distinct ways to assign to the ? characters. I do not see how the code given in the solutions handles this correctly. Basically, the provision: if((j