[일반] 해커컵 A2 어케 품?

[익명(49.169)]

A C D1 풀고 D2 풀이 찾고 짜다가 끝났는데

A2 괜히 고민한 시간 없으면 D2 풀었을거같네 ㅠ

[대학원오지마세요(publfl)]

난 해싱했음

[익명(110.34)]

혹시 해싱한다음 XOR 누적합 쓰는 건가요...?

[대학원오지마세요(publfl)]

처음엔 XOR누적합 생각했는데 그거로는 홀짝성만 알 수 있지 개수는 못알아서 그냥 덧셈으로 계산함. 그러니까 각 숫자 x에 대응하는 hash(x)라는 숫자를 만들었을때, 왼쪽 부분의 합 hash(l) + hash(l+1) ... + hash(m)과 hash(m+1) + ... + hash(r)의 차이가 어떤 특정 숫자 r의 hash값 hash(r)이라고 판단되면 바로 YES때림.

[대학원오지마세요(publfl)]

해쉬충돌을 막기 위해서 hash값은 long long 범위에 mod P 취해줄때 P를 아주 큰값(나의 경우 9999999999999937)로 잡아줌

[익명(110.34)]

아하... 그럼 [1, 1e6]의 정수를 해싱할때는 { a, b, c } in [1, 1e6]인 a, b, c와 임의의 자연수 p, q, r에 대하여 p*hash(a) + q*hash(b) != r*hash(c)가 항상 성립하도록 해싱을 해야겠네요... 합으로 하는 건 생각 못했는데 아이디어 감사합니다 ㅠ 발전시켜서 풀어볼게요

[대학원오지마세요(publfl)]

linearly independent하게 해싱할 수 있으면 좋지만 꼭 그걸 너무 의식할 필요는 없어요. 어짜피 적당히 랜덤하게 해쉬값을 크게 잘 줬다면 충돌이 일어날 일이 적으니까요. 왜냐하면 앞에 붙는 계수가 전부 N이하고 N은 100만까지기 때문에. 저도 그냥 아무랜덤 박았는데 통과됐으니

[익명(110.34)]

와 AC! 덕분에 하나 배워갑니다... b