随机打乱防hack

What · 是什么

随机打乱（random shuffle）是一种'防 hack'预处理：在算法执行前用随机数生成器打乱输入顺序，使确定性构造的'最坏数据'（针对固定顺序/固定哈希/固定枢纽的快排、固定 base 的字符串哈希、固定遍历顺序的算法）失效。在 Codeforces 的 hack 机制下，选手代码若对输入顺序、哈希 base、随机种子敏感，就会被构造数据卡掉；shuffle 或随机化参数能让攻击者无法预知代码行为。经典场景：随机化快速排序（随机选枢纽避免 O(n²) 退化）、随机 base/模数的字符串哈希（防碰撞构造）、随机增量法（见 random-technique）、std::random_shuffle 防止按特定顺序触发的退化分支。

Why · 为什么

How · 实现

伪代码

import random
random.seed()  # 默认系统熵
arr = [...]
random.shuffle(arr)  # Fisher-Yates 均匀洗牌
# 或固定种子便于复现: random.seed(1234)

# 随机化快排: 每次随机选 pivot 或先 shuffle
# 随机哈希 base: base = random.randrange(2**20, 2**30)
# 注意: 防 hack 需每轮不同种子

Python 实现

import random


def randomized_quicksort_median(a):
    """随机化快排: 随机选枢纽避免最坏情况"""
    if len(a) <= 1:
        return a[:]
    pivot = a[random.randrange(len(a))]
    lo = [x for x in a if x < pivot]
    eq = [x for x in a if x == pivot]
    hi = [x for x in a if x > pivot]
    return randomized_quicksort_median(lo) + eq + randomized_quicksort_median(hi)


def fisher_yates_shuffle(arr):
    """手动 Fisher-Yates: 验证均匀性"""
    a = arr[:]
    for i in range(len(a) - 1, 0, -1):
        j = random.randrange(i + 1)
        a[i], a[j] = a[j], a[i]
    return a


def sort_with_shuffle(arr, seed=None):
    """防 hack: 先 shuffle 再排序 (快排类算法消除最坏情况)"""
    rng = random.Random(seed)
    a = arr[:]
    rng.shuffle(a)
    a.sort()
    return a


if __name__ == "__main__":
    random.seed(42)

    # 随机化快排正确性
    for _ in range(200):
        n = random.randrange(1, 40)
        a = [random.randrange(10) for _ in range(n)]
        assert randomized_quicksort_median(a) == sorted(a)

    # shuffle+sort 与排序一致
    for _ in range(100):
        n = random.randrange(1, 50)
        a = [random.randrange(100) for _ in range(n)]
        assert sort_with_shuffle(a, seed=7) == sorted(a)

    # Fisher-Yates 均匀性: 统计每个元素到各位置频率近似均匀
    n = 6
    cnt = [[0] * n for _ in range(n)]
    trials = 20000
    for _ in range(trials):
        p = fisher_yates_shuffle(list(range(n)))
        for pos, val in enumerate(p):
            cnt[val][pos] += 1
    for v in range(n):
        for pos in range(n):
            assert abs(cnt[v][pos] / trials - 1.0 / n) < 0.02, (v, pos)

    # 不同种子结果不同(防 hack 的关键)
    a = list(range(50))
    s1 = sort_with_shuffle(a, seed=1)
    s2 = sort_with_shuffle(a, seed=2)
    assert s1 == s2 == sorted(a)  # 排序结果相同但执行顺序不同

    print("random-shuffle tests passed")

易错点

• 固定种子/忘调 srand => 随机化名存实亡，可被 hack
• random_shuffle 在旧标准下不是均匀的，用 std::shuffle 或 Fisher-Yates
• shuffle 不能'修复'算法本身的逻辑错误
• 对内存/缓存敏感问题，shuffle 反而可能使局部性变差
• OI/ICPC 正式赛一般不 hack，但防构造仍是稳健习惯

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/random/
• Wikipedia✓ https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle