문제: 두 정수의 쌍 (a, b) 중에서, 1 ≤ a, b ≤ N 이면서, a를 b로 나눈 나머지가 K 이상인 것의 갯수를 세시오.
풀이: mod를 규칙적으로 보기 위해서는 b가 고정되어있으면 편하기 때문에, b를 고정시켜 놓습니다. b를 고정시킨 경우에는 어떤 수를 b로 나눈 나머지는 0, 1, 2, 3, ..., b-1 까지 갔다가, 다시 0부터 시작해서 1씩 증가하고, b-1 다음엔 0으로 돌아온다는 사실을 알 수 있습니다. 그래서 이렇게 돌아가는 수열 중에서 K 이상인 것의 갯수를 세는 것은, 반복되는 부분인 0, 1, 2, 3, ..., b-1이 몇번 반복 되는가와, 가장 마지막에 어떤식으로 수열이 끝나는지를 알면 알 수 있습니다. 자세한 수식은 코드의 수식을 보면 알 수 있습니다.
문제: 길이 N의 두 수열 a와 b가 주어진다. 모든 가능한 i와 j에 대해서 ai+bj의 합 N2개를 모두 XOR 한 값을 구하시오.
풀이: 모든 합을 구해서 XOR하는것은 구하기 때문에, XOR을 구할때 비트별로 볼 것 입니다. 우리가 어떤 특정한 2B 에 해당하는 비트를 볼 때, 그 위에 있는 비트는 영향을 주지 않습니다. 중요한 것은 우리가 구하려는 비트(2B)에 있는 값과, 그보다 하위 비트(작은 두 수를 더해서 2B의 비트에 영향을 줄 수 있음)에 있는 값 입니다. 한 비트에 대해서 XOR은 1이 홀수개 있는지 짝수개 있는지 묻는 연산이기 때문에, 우리는 결국에는 해당하는 비트의 1의 홀짝성을 알려주면 됩니다. 즉, 이 비트에 영향을 홀수번 주었나, 짝수번 주었나를 묻는 문제입니다.
일단 우리가 구하려는 비트 부터 살펴봅시다. 한 원소의 구하려는 비트가 1이라는 것은, 합 N개의 비트에 영향을 주었다는 의미입니다. 그래서 우리는 수열에 해당하는 비트의 원소가 몇개 있는지를 살펴보면 됩니다. 이제 우리가 구하려는 비트에 영향을 끼치는 갯수는 구했습니다.
이 후에는, 우리가 구하려는 비트보다 하위 비트에 영향을 주는 갯수만 세면 됩니다.
그래서 우리는 이 문제를 비트마다 구하는 문제로 바꾸면, 각 수열의 원소는 2B 보다 작고, 2B에 해당하는 비트가 0인지 1인지를 구하는 문제가 됩니다. 2B에 해당하는 비트가 0인지 1인지 구하는 문제이지만, 어떤 수열의 두 원소의 합은 2B의 두배를 넘지 못하기 때문에, 결국 합해서 2B보다 큰 합의 갯수를 세는 문제로 바뀝니다. 이 문제는 sliding window를 사용하거나, 아니면 binary search를 사용해서 간단하게 구할 수 있습니다. 어떤 한 원소가 x이면, N-x보다 크거나 같은 수의 갯수를 std::lower_bound 등을 이용해 간단하게 세어 줄 수 있습니다. 제 구현은 후자를 사용했고 코드는 다음과 같습니다.
문제: A와 B가 주어졌을 때, 흰색 connected component의 갯수가 A개, 검정색 connected component의 갯수가 B개인 격자를 아무거나 찾아서 출력하시오.
풀이: 이것은 저의 풀이고, 다양한 풀이가 존재할 수 있습니다.
A가 1인 경우를 풀려고 해 봅시다. 일단 B가 0이면, 흰색으로 전체를 덮으면 됩니다. 여기서 B가 매우 크다고 해 봅시다. 그러면 흰색 component에 검정색 component 여러개를 끼워넣는 방법이 되어야 합니다. 그래서 우리는 흰색 component에 검정색 component를 서로 영향을 주지 않게 흰색끼리 연결되어있는 상태로 추가할 수 있습니다. 마치 수박에 있는 수박씨 처럼 흰색에다가 검정색으로 점을 서로 띄어서 찍어주면 됩니다. 이럴 경우에는 A가 1인 경우를 풀 수 있습니다. B를 추가하는게 점을 찍는것 입니다.
마찬가지로, 하얀색을 한 칸 추가할 수 있는 환경을 만드려면, 검정색으로 전체를 덮으면 됩니다.
저는 하얀색과 검정색을 반 반 나눠서 칠한 후 (A = B = 1), 검정색과 하얀색으로 점을 B-1, A-1개 각각 찍는데 서로 최소 2씩 거리가 나게 찍었습니다. 이렇게 찍은 경우에는 하얀색도 검정색도 배경은 연결되어 있다는 것을 알 수 있습니다.
이 문제는 다양한 풀이가 존재하고, 우리가 만들어야하는 격자의 크기가 작을 경우에 만들 수 있는가? 를 물어보는 문제도 재밌을 것 같습니다.