Zenn
💡

競プロ解説 [ABC250E]

2024/08/30に公開
Rust
AtCoder
tech

はじめに

本記事は、日々の精進で出会った問題の一部を丁寧目に解説することで、筆者と読者のアルゴリズム力を向上させることを目的としています。

問題

解説

本問題は集合の比較に関する問題です。2 つの集合を愚直に比較するには、サイズが異なるときは O(1)、一致するときは O(N) の計算量が必要になります。本問題では、集合を高速に比較することが求められています。

Zobrist hashing

2 つの集合を O(1) で比較する方法としてZobrist hashingが知られています。アルゴリズムの概要は次の通りです。

  1. 集合の各要素に乱数を割り振る
  2. 要素に対応する乱数のXORをその部分集合のハッシュ値とする

本問題では u32 の要素を改めて u32 の乱数に置き換えています。これはムダな操作ではありません。次の例を考えてみましょう。

集合 S = \{ 0, 1, 2, 3, 4, 5, 6, 7 \} を考えます。部分集合 \{ 0, 7 \}, \{ 1, 6 \}, \{ 2, 5 \}, \{ 3, 4 \} に XOR hashing を施すと、いずれも 7 になってしまいます。

このようにある種の入力に対してXOR hashingは脆弱です。XOR hashingを安全に行うために必要な条件を明らかにするために、もう少し考察を進めます。

まず、連続値に弱いことは明らかです。さらに値の範囲が狭いことも問題です。たとえば \{ 0, 2, 5, 7 \} を考えてみるとわかります。Zobrist hashingでは、乱択アルゴリズムを活用して（u32 の範囲で）疎らに割り振ることでこうした問題を解決しています。

最後に衝突確立を考えます[1]。考慮する部分集合の数が \lfloor 2^n \rfloor であり、それぞれのハッシュ値が n + m ビットであるとします。部分集合のハッシュ値もランダムに選ばれると仮定すると、衝突しない確率は

\prod_{i = 1}^{2^n}\Big( 1 - \frac{i - 1}{2^{n + m}} \Big) \sim \Big( 1 - \frac{1}{2^{n + m}} \Big)^{2^{n + m - m}} \sim \exp(-2^{-m})

ここで、ネイピア数の定義[2]を用いています。本問の制約では (n, m)=(17, 15) であり、衝突しない確率は 99.997\% です。余談ですが、ハッシュ値を u64 にとると、衝突する確率は 7 \times 10^{-13}\% になります。

回答例

use proconio::{fastout, input, marker::Usize1};
use rand::RngCore;
use rustc_hash::{FxHashMap, FxHashSet};

#[fastout]
fn main() {
    let (acc_hashed_a, acc_hashed_b) = {
        input! { n: usize, a: [u32; n], b: [u32; n], }

        let mut rng = rand::thread_rng();
        let hash_dict = FxHashMap::from_iter(
            // iter.sort_unstable().dedup() や iter.unique() より高速
            // itertools の unique() は標準ライブラリの HashMap を用いている
            FxHashSet::from_iter(a.iter().chain(b.iter()))
                .into_iter()
                .map(|v| (*v, rng.next_u32())),
        );

        let acc_hash = |src: Vec<u32>| {
            let mut res = Vec::with_capacity(src.len());

            let mut used = FxHashSet::with_capacity_and_hasher(
                src.len(), Default::default()
            );
            let mut hash = 0;
            for elem in src {
                if used.insert(elem) {
                    hash ^= hash_dict[&elem]
                }
                res.push(hash)
            }

            res
        };

        (acc_hash(a), acc_hash(b))
    };

    input! { q: usize, }
    for _ in 0..q {
        input! { x: Usize1, y: Usize1, }

        if acc_hashed_a[x] == acc_hashed_b[y] {
            println!("Yes")
        } else {
            println!("No")
        }
    }
}
脚注

  1. https://research.cs.wisc.edu/techreports/1970/TR88.pdf より引用・改変 ↩︎

  2. https://manabitimes.jp/math/714 ↩︎

Discussion