顺便说一下,据说在 G○○gle Code Jam 地区赛上坐在右边座位的男人的 ID 是 rng_58。 我记得在东京大学时期,有个类似 ID 的同伴,但我的同伴一个都不缺都是美少女。 我感觉她好像是那种所谓的无表情神秘系角色。
也就是说,他是个不认识的男人。rng 是什么缩写呢? 大概是 Random Number Generator(随机数生成器)没错。 他应该擅长使用随机化算法吧。
顺便说一下,使用随机数的平衡二叉搜索树 Treap, 在 2011 年左右的编程竞赛中似乎经常被使用, 但到了 20XX 年的现在,已经不太使用了。
当时 Treap 因为实现简单而与 Splay 树和 Scapegoat 树一起被广泛使用。 进入 20XX 年,在这个每天都会举行拼命的程序设计竞赛的世界里, 光凭实现稍微简单一些的这种理由是绝不可能被采纳的。 每个人都在考虑让程序尽可能更快, 而成为世界大赛选手的话,能够在十几秒内写出 Left-leaning 红黑树也是理所当然的。
例如,Treap 比红黑树慢的原因,据说是因为高度的常数倍起了作用。 在这里,让我们冷静地将其数值化地考察,从而恢复内心的平静。
問題
将键值设为实数的 Treap N 插入 n 个随机元素时, 高度为 h (h = 0, 1, …, N - 1) 的概率是多少。 下面,将做更详细的说明。
Treap 是一种使用随机数的平衡二叉搜索树。 每个节点除了有键外,还有一个叫做优先度的值。 这里,键和优先度都是 0 减去 1 以内的实数值。 在 Treap 中,以下两个条件总是保持的。
- 关于键的条件
- 对于每个节点,其左子节点及其以下的节点具有比自己小的键
- 对于每个节点,其右子节点及其以下的节点具有比自己大的键
- 关于优先度的条件
- 对于每个节点,其子节点具有比自己小的优先度
下图是 Treap 的一个例子。 每个节点的上方写着键,下方写着优先度。
由 7 个节点组成的 Treap 例子。
插入操作如下进行。 插入的键为 x 。 删除
- 插入的新节点的优先级 p 该值应乘以 0 减去 1 从到 的均匀分布中随机决定。
- 与普通二叉搜索树相同,首先忽略优先级插入新节点。
- 重复必要次数的旋转操作,使新节点满足优先级条件并向上提升。
关于树的旋转操作,已在附录章节中详细描述,请参考。
下图是刚才例子中插入一个键为 0.5、优先级为 0.7 的顶点的过程示例。
首先忽略优先级,节点被插入。
进行旋转,新节点升到上方。
再次进行旋转,由于满足优先级条件,插入结束。
对空的 Treap N 添加若干键, 还是 0 减去 1 以内的均匀分布随机选择并插入。 最终高度为 h 的概率, 请对每个 h = 0, 1, …, N - 1 求出。 此外,假设实数可以以足够的精度处理, 例如两个节点的优先级相等的概率可以视为 0。 另外,高度是从根节点到各节点必须经过的边的最大数量。
入力
个整数的一行 N 被写了。
出力
输出是 由 N 行组成。 第 i 行输出高度为 i - 1 的概率。 数值小数点后显示位数不限。
制約
- 1 ≤ N ≤ 3 × 104
- 要输出的值为 打印除以 10 - 5 以下的误差也可以包含在内。
入出力例
入力例 1:
1
输入示例 1 的输出示例:
1.0
入力例 2:
2
输入示例 2 的输出示例:
0.0000000000 1.0000000000
補足
树的旋转操作有右旋和左旋。右旋是将下面两个图中的第一个状态变为第二个状态的操作,左旋是将下面两个图中的第二个状态变为第一个状态的操作。
右旋之前,或者左旋之后
右旋之后,或者左旋之前
在 Treap 中,如果要提升的节点是其父节点的左子节点,就对要提升的节点应用如图中将其变为 P 的右旋;如果要提升的节点是其父节点的右子节点,就应用如图中将其变为 Q 的左旋。
想了解更多关于树的旋转操作的内容,请参考例如以下内容。
关于 Treap,想了解更多信息,可以参考例如以下内容。