[codeforces] 1978E, 1957D, 1977D

1978E. Computing Machine (Difficulty : 2000)

문제 링크

풀이

이 문제는 우리가 확인 중인 $a$의 부분 문자열에서 첫번째 왼쪽, 두번째 왼쪽, 첫번째 오른쪽, 두번째 오른쪽을 제외한 나머지는 원래 문자열에서 그대로 연산을 적용했을때와 동일하다는것을 캐치하면 쉽게 풀 수 있습니다.
즉, 일단 원래 $a$와 $b$에서 연산을 적용한 다음 위에서 언급한 네 부분만 확인해주면 됩니다.
연산을 적용한 후의 문자열을 각각 $a', b'$이라고 하겠습니다. 그럼 아래의 경우에만 $a'_{i} = 1$이지만 부분문자열에서 연산을 하면 0인 경우입니다.

즉, 누적합을 사용에서 $a'$에서의 1의 갯수를 구한 뒤 위 네가지 경우에 해당하는 경우만 빼주면 됩니다. 시간복잡도는 $O(n+q)$입니다.

1957D. A BIT of an Inequality (Difficulty : 1900)

문제 링크

풀이

$f(x, y) \oplus f(y, z) = f(x, z) \oplus a_{y}$입니다. 그리고 $f(x, z) \oplus a_{y} > f(x, z)$를 만족하려면 $a_{y}$에서 비트값이 1인 최고 비트에서 f(x, z)가 0이면 됩니다.

$l[i][b]$를 $0, f(1, 1), f(1, 2), \cdots ,f(1, i)$ 중에서 $b$번째 비트가 1인 값의 갯수라고 하고 $r[i][b]$를 $f(1, i), f(1, i+1), \cdots , f(1, n)$ 중에서 $b$번째 비트가 1인 값의 갯수라고 하고 한다면 각 $y$에 대해서 $a_{y}$의 비트값이 1인 최고 비트가 $b_{y}$번째 비트라고 할 때, 순서쌍 $(x, y, z)$의 갯수는 $\displaystyle \sum_{y = 1}^{n} \left( l[y-1][b_{y}] \cdot r[y][b_{y}] + (y-l[y-1][b_{y}]) \cdot (n+1-y-r[y][b_{y}]) \right)$ 가 됩니다. $l$과 $r$을 미리 전처리 한 뒤 계산하면 되고 시간복잡도 $O(n)$에 해결할 수 있습니다.

1977D. XORificator (Difficulty : 2300)

문제 링크

풀이

상당히 여러모로 고생했던 문제입니다.... 풀이는 금방 떠올렸는데 구현 미스로 AC 받는것도 꽤나 고생이였고 AC를 받은 풀이가 핵 당하기 너무 좋은 풀이여서 핵을 고려하면 어떻게 풀면 좋을지 오랜 시간 고민하고 에디토리얼 보면서 공부한 문제였습니다.

먼제 제 풀이는 이렇습니다. $j$번째 열을 특별하게 만들려고 하는데 $(i, j)$만 1, 나머지는 0으로 만들려고 합니다. 근데 이렇게 되면 그리드 전체의 상태가 유일하게 결정됩니다. 다시 말해 각 행의 XORificator 사용 여부도 유일하게 결정 된다는 이야기이고 이를 이용하여 이진수로 표현하는것이 가능해집니다. (XORificator을 사용하면 1, 아니면 0)

해당 값을 $s_{i, j}$라고 하겠습니다. 우선 이 값을 그대로 사용하는것은 무리가 있습니다. 가능한 값의 상한이 $2^{300000}-1$이기 때문입니다. 그래서 $s_{i, j} \mod 1000000007$을 해시값으로 해서 문제를 해결하려 했으나 저격 데이터가 있는지 WA를 받더군요. 그래서 순서쌍 $(s_{i, j} \mod 1049999827, s_{i, j} \mod 1049999903)$을 해시값으로 사용해봤고 AC를 받았습니다.

하지만 이 풀이는 핵 당하기 너무 좋은 풀이였습니다. 다시 말해 저격 데이터를 쉽게 만들 수 있는 풀이였습니다. 그래서 사용할 소수를 여러개 정해두고 랜덤으로 서로 다른 두개의 소수를 뽑은 뒤 해당 소수들로 해싱을 진행하는 방식으로 풀이를 바꾸면 핵에도 대처가 가능하지 않을까 생각합니다. 사용할 소수를 최대한 많이 뽑아둔다면 저격당할 확률도 크게 낮아져 핵 당할 걱정은 거의 안해도 되겠죠. 다만 미리 사용할 소수들을 따로 뽑아서 하드 코딩을 해주거나 랜덤으로 아무 수나 뽑을 때마다 소수 판정을 해줘야 한다는 단점이 있습니다.

그래도 풀이가 마음에 안들어서 에디토리얼을 따로 봐봤습니다. 에디토리얼의 풀이는 다음과 같습니다.

먼저 $n$개의 정수를 랜덤으로 뽑습니다. 그리고 XORificator를 사용하는 행에 해당하는 정수 값들을 전부 xor합니다. 이걸 2번 해주고 그 두 값을 순서쌍으로 묶어서 이걸 해시값으로 사용합니다.

이러한 해싱을 Zobrist hashing이라고 부르는것 같습니다. 이렇게 하면 해싱에 사용할 값들을 다른 판별 로직 없이 랜덤으로 뽑을 수 있어 제 풀이 보다 확실히 좋다는 생각이 들었습니다. 랜덤으로 뽑는 값의 범위도 충분히 크게 잡아준다면 해시 충돌이 발생할 확률이 매우 작아 사실상 AC를 받을 수 있고 핵을 당할 확률도 매우 작겠죠.

시간복잡도는 해시테이블을 사용하면 $O(nm)$입니다.