問題
$Q$ 個のクエリからなるストリームを処理せよ。クエリには以下の2種類がある：
add x v: 要素 $x$ ($1 \le x \le 10^9$) にカウント $v$ ($1 \le v \le 10^4$) を加算する。query x: 要素 $x$ のカウントの推定値を出力する。
Count-Min Sketch を実装し、各 query に対して推定値を出力せよ。全クエリ終了後、Heavy Hitter（推定カウントが全加算量の $1/k$ 以上の要素）を辞書順で列挙せよ。
制約
| パラメータ | 範囲 |
|---|---|
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
| $k$ | $1 \le k \le 100$ |
| $d$（行数） | $1 \le d \le 5$ |
| $w$（列数） | $1 \le w \le 10^4$ |
| $x$（要素ID） | $1 \le x \le 10^9$ |
入出力例
入力例 1
6 4 2 10
1000000007 1
999999937 3
add 5 10
add 3 7
add 5 5
query 5
query 3
query 1出力例 1
15
7
0
5最後の行は Heavy Hitter: 総加算量 22、閾値 22/4=5.5、推定値≥5.5 は要素 5（推定15）のみ。
概念図: Count-Min Sketch 行列
ヒント（段階的開示）
ヒント1: 方向性
add x v では各行 $i$ のセル $C[i][h_i(x)]$ に $v$ を加算する。query x では $\min_i C[i][h_i(x)]$ を返す。
ヒント2: アプローチ
- $d \times w$ のゼロ行列を初期化
add x v: 全行 $i$ でC[i][h_i(x)] += vquery x:min(C[i][h_i(x)] for i in range(d))- Heavy Hitter: 全加算量 $S$ を管理し、クエリ後に
query(x) * k >= Sを満たす要素を列挙
ヒント3: コード骨格
class CountMinSketch:
def __init__(self, d, w, hash_params, MOD=10**9+7):
self.d = d; self.w = w; self.hp = hash_params; self.MOD = MOD
self.C = [[0]*w for _ in range(d)]
def _hash(self, i, x):
a, b = self.hp[i]
return ((a * x + b) % self.MOD) % self.w
def add(self, x, v):
for i in range(self.d):
self.C[i][self._hash(i, x)] += v
def query(self, x):
return min(self.C[i][self._hash(i, x)] for i in range(self.d))模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
line1 = list(map(int, input().split()))
Q, k, d, w = line1
MOD = 10**9 + 7
hash_params = []
for _ in range(d):
a, b = map(int, input().split())
hash_params.append((a, b))
C = [[0] * w for _ in range(d)]
def _hash(i, x):
a, b = hash_params[i]
return ((a * x + b) % MOD) % w
def add(x, v):
for i in range(d):
C[i][_hash(i, x)] += v
def query(x):
return min(C[i][_hash(i, x)] for i in range(d))
total = 0
elements = set()
output = []
for _ in range(Q):
parts = input().split()
if parts[0] == 'add':
x, v = int(parts[1]), int(parts[2])
add(x, v)
total += v
elements.add(x)
else:
x = int(parts[1])
output.append(str(query(x)))
print('\n'.join(output))
# Heavy Hitters: query(x) * k >= total
heavy = sorted(x for x in elements if query(x) * k >= total)
print('\n'.join(map(str, heavy)))
solve()Step-by-Step 解説
Step 1: Count-Min Sketch の設計原理
$d$ 個の独立なハッシュ関数（Carter-Wegman 型: $h_i(x) = (a_i x + b_i \bmod p) \bmod w$）を用意し、$d \times w$ のカウンタ行列を管理する。異なる要素がハッシュ衝突した場合、そのセルは過大カウントされる（過小評価はしない）。
Step 2: add 操作 $O(d)$
要素 $x$ に値 $v$ を加算するとき、全行 $i$ のセル $C[i][h_i(x)]$ に $v$ を加える。
Step 3: query 操作 $O(d)$
$d$ 行の最小値を返す。少なくとも1行でハッシュ衝突がなければ真の値を返す。誤差 $\epsilon$ の確率的上界：衝突期待値 $\le e/w \cdot S$（$S$=総加算量）、失敗確率 $\le (1/e)^d$。
Step 4: Heavy Hitters 列挙
真の頻度 $f(x) \ge S/k$ の要素を検出したい。CMS の推定値 $\hat{f}(x) \ge f(x)$ であるため $\hat{f}(x) \ge S/k$ でフィルタリング。整数比較で精度を保つため query(x) * k >= total を使う。
Step 5: 計算量
| 処理 | 計算量 |
|---|---|
| add / query 各1回 | $O(d)$ |
| 全クエリ | $O(Qd)$ |
| Heavy Hitters 列挙 | $O(|E| \cdot d \log |E|)$（$|E|$: ユニーク要素数） |
| 空間 | $O(d \cdot w)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 浮動小数点比較 | query(x) >= total / k で精度ロス |
query(x) * k >= total で整数比較 |
| Heavy Hitter に query 時の要素が漏れる | add した要素だけ追跡 | elements セットに add 時に追加 |
| total を query でも更新してしまう | 読み取り操作と書き込み操作の混同 | add 時のみ total += v |
次のステップ
発展問題: Count-Min Sketch を削除クエリ（カウント減算）にも対応させよ。さらに CMS と Space Saving Algorithm を組み合わせて、誤差保証付きの Top-K Heavy Hitters を返せ。