Codeforces Round 1125 (Div. 3) C - Unrequited Love
長さ の整数列 があります(、)。 に対して、鍵 の組を「トライアド 」と呼び、その値を とします。
鍵を共有せず、値が等しい 2 つのトライアドの組(順序は区別しない)の個数を求めてください( の総和 )。
とおきます。
鍵を共有するのはどんなときか
Section titled “鍵を共有するのはどんなときか”トライアド の鍵は と です。 が奇数なら偶奇が違うので共有しません。 なら離れすぎていて共有しません。したがって、鍵を共有するのは または のときだけです。
余事象で数える
Section titled “余事象で数える”鍵の共有を気にせずに、値が等しいペアをすべて数えてから、鍵を共有するペアを引きます。
- 値が等しいペアの総数: をソートすると、同じ値が連続して並びます。同じ値が 個あれば、そこから 個のペアが作れます。
- 鍵を共有するペア: となる の個数と、 となる の個数を足したものです。
答えは前者から後者を引いたものです。計算量はソートがあるので です。
補足:辞書で数えるとハックされる
Section titled “補足:辞書で数えるとハックされる” と等しい ()の個数を、Counter などの辞書で数えながら左から見ていく方法も考えられます。ただ、Python でこの方法を提出したところ、PyPy でも TLE になりました(テスト 7)。
テスト 7 は、奇数番目の要素がすべて の入力です。そのため奇数位置の はすべて になり、辞書のキー が約 回検索されます。一方、偶数位置の は、キー を検索するときにたどる位置をほかのキーで埋め尽くすように作られていると考えられます。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 を数え、 を足しています。そのあと、位置の差が と で値が等しいものを引いています。
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();}左から順に見て、トライアド と組になる を数えています。
- の分は、
c(値ごとの個数を持つstd::map)で数えます。 - が と の分は、直近 4 個の値を持つ
dで個別に確かめます。
が と のペアは鍵を共有するので数えません。
使用ライブラリ:cpp_include@6e9980e