Day 026-Q2 — 確率的データ構造 (Count-Min Sketch + HyperLogLog)

2026-05-09 赤色 Master / Phase 8+ ★★★★★★★★★ Sketches / Probabilistic

問題

整数ストリームに対する ADD x, FREQ x（誤差 $\varepsilon n$）、DISTINCT（相対誤差 0.1）を処理。

制約

$1 \le Q \le 2 \times 10^5$
$1 \le x \le 10^9$
$\varepsilon = 0.01, \delta = 0.01$

入出力例

入力例 1

8
ADD 1
ADD 2
ADD 1
ADD 3
ADD 1
FREQ 1
FREQ 2
DISTINCT

出力例 1

3
1
3

ヒント (段階的開示)

ヒント1: 方向性
Count-Min Sketch: $w \times d$ テーブル + universal hash。誤差確率 $\Pr[\hat f - f > \varepsilon n] \le \delta$。
ヒント2: アプローチ
HyperLogLog: ハッシュ下位 $b$ ビット = バケットID、残りの先頭0ビット数で $2^R$ を推定。調和平均で安定化。
ヒント3: 誘導
w = ceil(e/eps), d = ceil(ln(1/delta))。$\alpha_m \approx 0.7213/(1 + 1.079/m)$。

模範解答 (Python)

import sys
import math
import random
input = sys.stdin.readline

class CountMinSketch:
    def __init__(self, epsilon=0.01, delta=0.01):
        self.w = max(1, math.ceil(math.e / epsilon))
        self.d = max(1, math.ceil(math.log(1.0 / delta)))
        self.table = [[0] * self.w for _ in range(self.d)]
        p = (1 << 31) - 1
        self.hashes = [(random.randint(1, p-1), random.randint(0, p-1), p) for _ in range(self.d)]
    def add(self, x):
        for i, (a, b, p) in enumerate(self.hashes):
            self.table[i][((a*x+b)%p)%self.w] += 1
    def query(self, x):
        return min(self.table[i][((a*x+b)%p)%self.w] for i, (a,b,p) in enumerate(self.hashes))

class HyperLogLog:
    def __init__(self, b=10):
        self.b = b
        self.m = 1 << b
        self.M = [0] * self.m
        if self.m == 16: self.alpha = 0.673
        elif self.m == 32: self.alpha = 0.697
        elif self.m == 64: self.alpha = 0.709
        else: self.alpha = 0.7213 / (1 + 1.079 / self.m)
    def _hash(self, x):
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb
        x = x ^ (x >> 31)
        return x & ((1 << 64) - 1)
    def add(self, x):
        h = self._hash(x)
        j = h & (self.m - 1)
        w = h >> self.b
        leading_zeros = 0
        for bit in range(64 - self.b, 0, -1):
            if w & (1 << (bit - 1)): break
            leading_zeros += 1
        rho = leading_zeros + 1
        self.M[j] = max(self.M[j], rho)
    def count(self):
        Z = sum(2.0 ** (-m) for m in self.M)
        E = self.alpha * self.m * self.m / Z
        if E <= 2.5 * self.m:
            V = self.M.count(0)
            if V > 0:
                E = self.m * math.log(self.m / V)
        elif E > (1 << 32) / 30:
            E = -(1 << 32) * math.log(1 - E / (1 << 32))
        return round(E)

def solve():
    cms = CountMinSketch(0.01, 0.01)
    hll = HyperLogLog(10)
    Q = int(input())
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == "ADD":
            x = int(line[1]); cms.add(x); hll.add(x)
        elif line[0] == "FREQ":
            out.append(str(cms.query(int(line[1]))))
        elif line[0] == "DISTINCT":
            out.append(str(hll.count()))
    print('\n'.join(out))

solve()

Step-by-Step 解説

1Count-Min Sketch
行ごと独立 hash でカウントし、最小値を取る（オーバーカウントが各行独立）。
2HyperLogLog
調和平均で $2^R$ 推定。バケット $m$ で分散させ相対誤差 $\approx 1.04/\sqrt m$。
3定数と補正
小カーディナリティは Linear Counting、大は $2^{32}$ 補正。
4Universal Hash
$h(x) = (ax+b) \bmod p \bmod w$ で 2-universal。

よくあるミス

ミス原因正しい書き方
rho オフバイワン0ビット数 vs 1+0ビット数rho = leading_zeros + 1
$\alpha_m$ 誤差m が小さい場合$m = 16, 32, 64$ は定数テーブル
delta の対数底の混乱math.log は自然対数

次のステップ

  • Count Sketch (+/- カウンタ)
  • Second Moment 推定 (JL)

自己評価

自分の回答

気づき・メモ