昨天 Code Jam 有一个题为 Falling Diamonds 的问题。全文可以在这里找到，但总结如下：
- 钻石沿 Y 轴落下。
- 如果一颗钻石与另一颗钻石点对点，它有 50/50 的机会向右或向左滑动，前提是它没有被阻挡。
- 如果钻石被阻止向一个方向滑动，它总是会向另一个方向滑动。
- 如果钻石在两个方向上都被阻挡，它将停止并停留在阻挡钻石上。
- 如果钻石撞到地面，它会埋到一半，然后停下来。
- 钻石的方向永远不会改变，即它会滑动或下沉，但不会翻滚。
- 目标是找到一颗钻石停留在给定坐标的概率，假设 N 颗钻石掉落。
上述要求基本上归结为钻石依次建造更大的金字塔，一次一层。
可以说，我无法让谷歌满意地解决这个问题。我从问题描述中得到了正确的样本，但在实际输入文件中失败了。理想情况下，我希望看到一个匹配的输入和正确的输出文件，我可以使用它来尝试找出我的错误。除此之外，我也欢迎对我的代码发表评论。
一般来说，我的方法是找出需要多少层才能拥有一个包含坐标的层。一旦我知道我在看哪一层，我就可以确定与我们试图到达的层和点相关的一些值。例如，当这一层为空时，金字塔中有多少颗钻石，有多少颗钻石可以堆叠在一侧，其余的则被迫相反，有多少必须向同一方向滑动才能到达所需的点等。
然后，我检查掉落的钻石数量是否导致无法到达该点（概率 0），或者保证我们将覆盖该点（概率 1）。挑战在于有可能但不能保证的中间地带。
对于中间地带，我首先检查我们是否下降到足以填充一侧并迫使剩余的下降向相反方向滑动。原因是在这种情况下，我们可以保证一定数量的钻石会滑到每一边，减少了我们需要担心的掉落数量，解决了边满时概率变化的问题。示例：如果 12 颗钻石掉落，则保证外层的每一侧都会有 2 颗或更多颗钻石，给定的一侧是否有 2、3 或 4 颗取决于仅 2 颗掉落的结果，而不是全部 6 颗的结果落在这一层。
一旦我知道有多少滴与成功相关，以及必须以相同的方式打破以覆盖这一点的数字，我就会总结必要的数字或更多的概率会以同样的方式发生。
正如我所说，我可以解决问题描述中的示例，但我没有得到输入文件的正确输出。不幸的是，我找不到任何东西告诉我正确的输出是什么，以便我可以将它与我得到的进行比较。这是我的代码（自从比赛结束以来，我已经花了相当多的时间试图调整它以获得成功并添加评论以防止自己迷路）：
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();
}
}