動画的企画法と確率の広がり

最近トップコーダーのオープン試合の中級問題に挑戦しています。　
更新。やっぱり確率ではなくて否定な確率が鍵になります。finding the positive probability at each node is nearly impossible, due to the possibility of multiple nodes' preceding the same node and of cyclic dependencies. However, computing the negative probability of each clue's not being found is trivial, as it is the product of one minus the marginals of all predecessors (by definition of joint probability, note that i is a predecessor of itself). Using the negative probability eliminates complications caused by the topology. The predecessor[i][j] map can be found using a triple for loop algorithm analogous to Floyd-Warshall. After finding a node's negative probability p, the positive probability is simply 1-p, and we can sum this quantity over all nodes to obtain the expected number of clues found.
The goal is to compute an expectation of a number of clues found, and the author attempted to compute expectation by summing the likelihood of each clue's being found. The dependency graph of this model is essentially a Markov chain with loops. What is ambiguous is in what values to propagate to successor nodes. In some cases, the entire probability should be propagated (ie if the successor has never been visited). However, in others, the "delta" representing the gain in the predecessor node over the successor needs to be propagated. The latter case arises in the case of loops and also when a predecessor has a higher index than its successor, who has already been "visited". Another difficult case is when a node is linked to multiple nodes which themselves have a dependency relationship. When a node j's probability is propagated to such a node k, any nodes i which j precedes(directly orindirectly) and which also are linked as direct predecessors to k must have their contributions to k subtracted from j's contribution. Also, nodes i which precede j and which directly precede k must, if j has passed its update to k ahead of it, subtract the part of j's contribution received from i from its own new contribution. The subtraction also holds for i when j precedes it, depending on the order in which nodes are traversed. Thus, a "deltas" two-dimensional array data structure must be maintained in order to determine the amounts subtracted (i.e. deltas[i][j] (for i) and deltas[j][i] (for j), if i and j share direct successor k).
依存関係を保存するデータ構成を設立する事が必要です。
The problems of cycles and multiple predecessors is non-trivial, and the determining factor of whether this algorithm works is whether the cumulative propagation probabilities in the deltas matrix are applicable to all cases.
The new approach is unlikely to work, though, as the (1-marginals) factor is counted when the delta is computed, but this value discounts the input of the other predecessors. でも確率の理論を考えれば通る方法があるかもしれません。If the joint probability of m and n is subtracted from n's contribution to a node x when m and n are both linked to it, then a dynamic programming model could work. However, this joint probability can be subtracted only once in computing P[x].