コンテンツにスキップ

ハッシュ

タグ「ハッシュ」の記事 1 件

Codeforces Round 1125 (Div. 3) C - Unrequited Love

長さ nn の整数列 a1,…,ana_1, \dots, a_n があります(6≤n≤2⋅1056 \le n \le 2 \cdot 10^5、∣ai∣≤104|a_i| \le 10^4)。1≤x≤n−41 \le x \le n - 4 に対して、鍵 x,x+2,x+4x, x + 2, x + 4 の組を「トライアド xx」と呼び、その値を ax+ax+2−ax+4a_x + a_{x+2} - a_{x+4} とします。

鍵を共有せず、値が等しい 2 つのトライアドの組(順序は区別しない)の個数を求めてください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

vx=ax+ax+2−ax+4v_x = a_x + a_{x+2} - a_{x+4} とおきます。

鍵を共有するのはどんなときか

Section titled “鍵を共有するのはどんなときか”

トライアド x<yx < y の鍵は {x,x+2,x+4}\{x, x+2, x+4\} と {y,y+2,y+4}\{y, y+2, y+4\} です。y−xy - x が奇数なら偶奇が違うので共有しません。y−x≥6y - x \ge 6 なら離れすぎていて共有しません。したがって、鍵を共有するのは y−x=2y - x = 2 または y−x=4y - x = 4 のときだけです。

鍵の共有を気にせずに、値が等しいペアをすべて数えてから、鍵を共有するペアを引きます。

  • 値が等しいペアの総数:vv をソートすると、同じ値が連続して並びます。同じ値が kk 個あれば、そこから (k2)=k(k−1)2\binom{k}{2} = \frac{k(k-1)}{2} 個のペアが作れます。
  • 鍵を共有するペア:vx=vx+2v_x = v_{x+2} となる xx の個数と、vx=vx+4v_x = v_{x+4} となる xx の個数を足したものです。

答えは前者から後者を引いたものです。計算量はソートがあるので O(nlog⁡n)O(n \log n) です。

補足:辞書で数えるとハックされる

Section titled “補足:辞書で数えるとハックされる”

vyv_y と等しい vxv_x(x<yx < y)の個数を、Counter などの辞書で数えながら左から見ていく方法も考えられます。ただ、Python でこの方法を提出したところ、PyPy でも TLE になりました(テスト 7)。

テスト 7 は、奇数番目の要素がすべて 00 の入力です。そのため奇数位置の vxv_x はすべて 00 になり、辞書のキー 00 が約 10510^5 回検索されます。一方、偶数位置の vxv_x は、キー 00 を検索するときにたどる位置をほかのキーで埋め尽くすように作られていると考えられます。Python の整数のハッシュ値は値そのものなので、キーが予測できればこのような入力を作れてしまいます。その結果、検索のたびに長い列をたどることになって TLE します。

対策としては、次のどちらかがあります。

  • 起動時に決めた乱数とキーの XOR をとってから辞書に入れる(ハックする側が衝突を狙えなくなる)
  • 上の解法のように、ハッシュを使わずにソートで数える

ここでは後者を採用しています。C++ の std::map は平衡二分木でハッシュを使わないので、辞書で数える方法でも問題ありません。

Python
from itertools import groupby
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = N - 4
v = [A[i] + A[i + 2] - A[i + 4] for i in range(M)]
ans = 0
for _, g in groupby(sorted(v)):
k = len(list(g))
ans += k * (k - 1) // 2
for i in range(M):
if i + 2 < M and v[i] == v[i + 2]:
ans -= 1
if i + 4 < M and v[i] == v[i + 4]:
ans -= 1
print(ans)

groupby(sorted(v)) で同じ値の並びごとに個数 k を数え、(k2)\binom{k}{2} を足しています。そのあと、位置の差が 22 と 44 で値が等しいものを引いています。

C++(std::map で数える)
#include "sh-library/base/all"
void solve() {
LL(N);
VL(A, N);
mll c;
ll ans = 0;
deque<ll> d;
rep(i, N - 4) {
ll t = A[i] + A[i + 2] - A[i + 4];
ans += c[t];
if (d.size() >= 1 && d[d.size() - 1] == t) {
ans++;
}
if (d.size() >= 3 && d[d.size() - 3] == t) {
ans++;
}
while (d.size() >= 4) {
c[d.front()]++;
d.pop_front();
}
d.push_back(t);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

左から順に見て、トライアド yy と組になる x<yx < y を数えています。

  • y−x≥5y - x \ge 5 の分は、c(値ごとの個数を持つ std::map)で数えます。
  • y−xy - x が 11 と 33 の分は、直近 4 個の値を持つ d で個別に確かめます。

y−xy - x が 22 と 44 のペアは鍵を共有するので数えません。

使用ライブラリ:cpp_include@6e9980e