AtCoderBeginnerContest228 D 問題 400 点 「D - Linear Probing」

問題リンク

問題概要

あるインデックスに値を割り当てることを考える。もし既に割り当て済みである場合はインデックスを 1 増やして割り当てが可能かチェックする。インデックスは 1«20 が上限であり，それを超えた場合は 0 に戻る。 割り当てクエリと参照クエリに分けられるので，クエリを実行したときの参照クエリで示されたインデックスの値を答えろ。

制約

解法

愚直に指定のインデックスから 1 つずつ確認していくと TLE になる。そこで，UnionFind の結合処理で行われるような親要素を結合の度に探していく処理を，割り当てクエリの度に実行することで処理を高速化する。

具体的には，はじめにparent = [i for i in range(N)]といった形で自分を親とする配列を用意し，P[i]に値を割り当てたらP[i] = i + 1とするように次に割り当てられる最も近いインデックスを記録しておく。ただ実際にはi+1が必ず次の割当先になるとは限らないので，再帰関数を用いてP[j] = jとなっている最も近いインデックスjを見つける。これは割り当てクエリのインデックスを探す場合にも使用できるので，インデックスを探索する必要がほとんどなくなる。

これは経路圧縮と呼ばれる手法らしく，各操作をならし計算量（償却）$\mathcal{O}(\log N)$で行うことができる。

したがって，すべての操作は$\mathcal{O}(N + Q\log N)$で行うことができ，十分高速に動作する。

お気持ち

公式解説では mod N を取らずに 1 « 20 - 1 と x の論理積を取って次の座標を計算していた。これによって 1 « 20 を超えた場合にはインデックスが 0 に戻る。かしこい～～

このような操作はハッシュテーブルのハッシュ探索手法でいうと開番地法(オープンアドレス法)の線形走査法というらしい。疑問なのは連続したハッシュの中間あたりを削除したときの次の割り当てで，無駄に空きができてしまって再割当てされないのではないかという気がする。二重ハッシュという方法があるらしいが，ちゃんと見ていない。以下が詳しく説明されていそうなので読んだほうがいいはず。

AC コード

import sys

sys.setrecursionlimit(10**9)

Q = int(input())
N = 1 << 20
A = [-1] * (N + 1)
P = [i for i in range(N)]
MASK = (1 << 20) - 1
ans = []


def find(x):
    global P
    if P[x] == x:
        return x
    else:
        P[x] = find(P[x])
        return P[x]


for _ in range(Q):
    t, x = map(int, input().split())
    if t == 1:
        idx = find(x % N)
        A[idx] = x
        P[idx] = find((idx + 1) % N)
    else:
        ans.append(A[x % N])
print(*ans, sep="\n")