c# - Google Code Jam 2013 R1B-坠落的钻石

Question

昨天的代码堵塞有一个题为“掉下来的钻石”的问题全文可在here中找到，但总而言之：
钻石从Y轴上掉下来。
如果一颗钻石击中另一颗钻石的点对点，它有50/50的机会滑向右侧或左侧，前提是它没有被阻止滑向右侧或左侧。
如果一颗钻石被阻止向一个方向滑动，它总是会向另一个方向滑动。
如果一颗钻石在两个方向都被阻塞了，它就会停下来停在阻塞的钻石上。
如果一颗钻石掉到地上，它会把自己埋到一半，然后停下来。
钻石的方向永远不会改变，即它会滑动或下沉，但不会翻滚。
其目的是在假设n个钻石下落的情况下，求出钻石在给定坐标处静止的概率。
以上的要求基本上归结为钻石建筑接连建造更大的金字塔，一层一层。
可以说，我没能解决这个问题，谷歌满意。我从问题描述中得到的样本是正确的，但是在实际的输入文件中失败了理想情况下，我想看到一个匹配的输入和正确的输出文件，我可以玩，以试图找到我的错误。除此之外，我也欢迎对我的代码发表评论。
一般来说，我的方法是找出需要多少层才能有一个包含坐标的层一旦我知道我在看哪一层，我就可以确定一些与我们试图到达的层和点相关的值比如这一层空了，金字塔里有多少钻石，在其他钻石被另一种方式挤压之前，有多少钻石可以堆积在一边，有多少钻石必须在同一方向滑动才能达到所需的点等等。
然后我检查钻石掉落的数量是否会导致无法到达该点（概率0），或者保证我们将覆盖该点（概率1）。这个挑战是在中间地带，在那里是可能的，但不能保证。
对于中间地带，我首先检查一下，看看我们的下落是否足够填满一个边，并迫使剩余的水滴向相反的方向滑动。原因是在这种情况下，我们可以保证一定数量的钻石会滑向每一边，这就减少了我们要担心的滴数，并解决了当一方充满时概率变化的问题。例如：如果有12颗钻石掉落，那么外层的每一面都会有2颗或更多的钻石，而不是这一层的所有6颗钻石中的每一面都有2颗、3颗或4颗。
一旦我知道有多少滴水与成功相关，而且为了涵盖这一点，必须以相同的方式打破的数字，我就求出必要的数字或更多的数字将以相同的方式消失的概率。
正如我所说的，我可以解决问题描述中的示例，但无法获得输入文件的正确输出不幸的是，我找不到任何东西告诉我正确的输出是什么，这样我就可以把它与我得到的进行比较。以下是我的代码（自从比赛结束后，我花了相当长的时间试图调整它以获得成功，并添加评论以防止自己迷失方向）：

protected string Solve(string Line)
{
    string[] Inputs = Line.Split();
    int N = int.Parse(Inputs[0]);
    int X = int.Parse(Inputs[1]);
    int Y = int.Parse(Inputs[2]);

    int AbsX = X >= 0 ? X : -X;
    int SlideCount = AbsX + Y;  //number that have to stack up on one side of desired layer in order to force the remaining drops to slide the other way.
    int LayerCount = (SlideCount << 1) | 1; //Layer is full when both sides have reached slidecount, and one more drops
    int Layer = SlideCount >> 1; //Zero based Index of the layer is 1/2 the slide count
    int TotalLayerEmpty = ((Layer * Layer) << 1) - Layer; //Total number of drops required to fill the layer below the desired layer
    int LayerDrops = N - TotalLayerEmpty; //how many will drop in this layer
    int MinForTarget; //Min number that have to be in the layer to hit the target location, i.e. all fall to correct side
    int TargetCovered; //Min number that have to be in the layer to guarantee the target is covered
    if (AbsX == 0)
    {//if target X is 0 we need the layer to be full for coverage (top one would slide off until both sides were full)
        MinForTarget = TargetCovered = LayerCount;
    }
    else
    {
        MinForTarget = Y + 1; //Need Y + 1 to hit an altitude of Y
        TargetCovered = MinForTarget + SlideCount; //Min number that have to be in the layer to guarantee the target is covered
    }

    if (LayerDrops >= TargetCovered)
    {//if we have enough dropping to guarantee the target is covered, probability is 1
        return "1.0";
    }
    else if (LayerDrops < MinForTarget)
    {//if we do not have enough dropping to reach the target under any scenario, probability is 0
        return "0.0";
    }
    else
    {//We have enough dropping that reaching the target is possible, but not guaranteed

        int BalancedDrops = LayerDrops > SlideCount ? LayerDrops - SlideCount : 0; //guaranteed to have this many on each side
        int CriticalDrops = LayerDrops - (BalancedDrops << 1);//the number of drops relevant to the probablity of success
        int NumToSucceed = MinForTarget - BalancedDrops;//How many must break our way for success
        double SuccessProb = 0;//Probability that the number of diamonds sliding the same way is between NumToSucceed and CriticalDrops
        double ProbI;
        for (int I = NumToSucceed; I <= CriticalDrops; I++)
        {
            ProbI = Math.Pow(0.5, I); //Probability that I diamonds will slide the same way
            SuccessProb += ProbI;
        }

        return SuccessProb.ToString();

    }
}

Answer 1

你的一般方法似乎适合这个问题，尽管最后一个概率的计算并不完全正确。
让我描述一下我是如何解决这个问题的。我们在看金字塔这些金字塔可以分配一个层，根据金字塔有多少钻石层的金字塔只有金刚石。层的金字塔有钻石。层的金字塔有钻石层的金字塔有钻石，等于。
鉴于此，我们可以计算出我们能够用给定数量的钻石建造的最大金字塔的层数：

layer = floor( ( sqrt( 1 + 8 * diamonds ) + 1 ) / 4 )

以及建造这个金字塔不需要的钻石数量。这些钻石将开始填充下一个更大的金字塔：

overflow = diamonds - layer * ( 2 * layer - 1 )

我们现在可以看到以下情况：
如果该点位于层1内，则它将被覆盖，因此1。
如果该点不在层2内（即下一个更大的棱锥体），则不会被覆盖，因此1 + 2 + 3。
如果该点位于层3内，则可能被覆盖，因此1 + 2 + 3 + 4 + 5。
因为我们只需要解决最后一个问题，所以我们可以稍微简化问题陈述：给定三角形的两边，n和1 + 2 + 3 + ... + 2*n-1每边都有一个固定的容量，最大的钻石数。一个配置(2 * n - 1) * n的概率是多少，其中layer表示右侧的菱形，p = 1.0表示左侧的菱形，layer + 1。
这个概率可以用伯努利的轨迹来计算：

P( nr ) = binomial_coefficient( overflow, k ) * pow( 0.5, overflow )

然而，这在一种情况下会失败：如果一方完全充满了钻石，概率就会改变。金刚石落在完全填充的一侧的概率现在是p = 0.0，而另一侧的概率是layer + 1。
假设以下情况：每边最多可以拿走4颗钻石，而剩下6颗钻石有趣的情况现在是0 <= p <= 1，因为在这种情况下，左侧将获得4个菱形。
六颗钻石怎么会掉下来。r表示向右走，而l表示向左走：
(nr, nl)=>对于每一颗钻石，每边的概率都是nr。这个案子和以前的案子没什么不同。这种情况发生的概率是nl。有4种不同的情况是这样的（nr + nl = overflow，0，1，P( 2 )）有10种不同的情况是这样的。案例数是从5中选择一个元素的方法数：r
最后一颗钻石会落在右边，因为左边已经满了。最后一个概率是右边1，左边0。这种情况发生的概率是l有4种不同的情况如下：l r l r l l
0.5=>最后两颗钻石将落在右侧，因为左侧已满。最后两个概率是右边1，左边0。这种情况发生的概率是pow( 0.5, 6 )。只有一种情况是这样的，因为rllllr。
一般的算法是假设最后一个lrlllr元素必然会到右边，然后计算每种情况下的概率（最后一个llrllr概率为lllrlr），并将每种概率乘以最后一个binomial_coefficient( 5, 2 ) = 10概率为l r l l l r的不同情况的数目。
请参阅以下代码pow( 0.5, 5 )将是binomial_coefficient( 4, 1 ) = 4菱形在右侧且左侧已满的情况下的概率：

p = 0.0
for i in range( nr + 1 ):
    p += pow( 0.5, overflow - i ) * binomial_coefficient( overflow - i - 1, nr - i )

现在，我们可以计算每个单独组合的概率l l l l r r，只需将pow( 0.5, 4 )的所有情况相加，k是仍然覆盖所需点的一侧的最小钻石数。
查看我用于此问题的完整python代码：https://github.com/frececroka/codejam-2013-falling-diamonds/blob/master/app.py