BOJ 18762 - Junk Problem (Python3)
어려운 난이도로 올라갈수록 PS 범위라고 생각하지도 않았던 발상을 사용해야 한다. 대표적인 예시로 현대대수를 쓰는 3904번 문제가 있고, 그리고 이 문제가 있다. 정말 상상도 못 하는 발상으로 문제가 풀리는데, 그 발상 난이도가 문제 난이도의 9할 정도를 차지하고 있다.
더 놀라운 점은 이 문제가 셋에서 중간 정도의 난이도를 가지고 있다는 것이다. Petrozavodsk Programming Camp의 문제들 난이도가 높은 것은 알고 있었지만, 플래티넘조차 없는 셋은 정말 처음 본다.
그럼 본격적으로 풀이에 돌입해 보자. 문제의 본문은 내가 임의로 번역을 좀 했다.
문제
위키피디아를 검색해서 무작위 참고 문헌을 읽는 것은 문제를 만드는 가장 좋은 방법이다.
\(N\)이 주어지면, 다음 조건을 만족하는 \(S\subseteq\{1,2,\cdots,N\}\)을 아무거나 하나 구하여라.
\(S\)의 원소 수는 \(\lfloor\sqrt{0.5N}\rfloor\) 이상이어야 하고, \(a,b\in S\)가 \(a<b\)라면, 이 둘의 bitwise XOR \(a\oplus b\)의 값은 모두 달라야 한다. 엄밀하게 말하자면, \(a,b,c,d\in S\)이 \(a<b, c<d\)이고 \(a\oplus b=c\oplus d\)이면 \(a=c, b=d\)가 성립해야 한다.
입력
첫 번째 줄에 정수 \(N\)이 주어진다. \((1\le N\le 10^7)\)
예제 입력)
49
출력
첫 번째 줄에 \(S\)의 원소 갯수 \(M\)을 출력한다.
두 번째 줄에 \(S\)의 원소 \(M\)개를 공백으로 구분하여 임의의 순서로 출력한다.
예제 출력)
4
1 2 3 4
내 코드
# Not Included #
고난이도 문제라 코드를 첨부하지 않는다.
이 문제의 살짝 다른 버전을 생각해 보자. Bitwise XOR 대신 그냥 합을 생각해 보자는 이야기이다. 정수 \(a<b, c<d\)에 대하여 \(a+b=c+d\)이 성립한다고 하자. 여기에 다른 한 조건이 주어지면 \(a=c, b=d\)를 얻을 수 있다. 당장 생각나는 것이 무엇인가? 그렇다, \(ab=cd\)이다. 이러면 이차방정식의 근과 계수의 관계에 의해서 \(a,b\)를 근으로 가지는 이차방정식과 \(c,d\)를 근으로 가지는 이차방정식은 완전히 동일하게 되기 때문.
조금 더 생각을 발전시켜 보면 \(a^3+b^3=c^3+d^3\)이라는 조건도 생각해 낼 수 있다. 왜냐하면 \(ab=\frac{(a+b)^3-(a^3+b^3)}{3(a+b)}\)이기 때문에. 그렇다면 \(a,b,c,d\)가 예를 들어 \(10^4\) 범위에 있다면, \(10^{12}a+a^3=f(a)\)로 두면, \(S=\{f(1), f(2), \cdots\}\)로 둘 시 \(S\)의 서로 다른 두 원소의 합이 다를 것이다.
그렇다면 bitwise XOR는 어떨까? 사실 이 bitwise XOR는 합이랑 크게 다를 바가 없다. 이진수 \(\sum a_i2^i\)를 \(F=\mathbb{F}_2(\beta)\)의 원소 \(\sum a_i\beta^i\)와 대응시킨다면 이진수의 bitwise XOR는 \(F\)의 두 원소의 합이 된다. 그렇다면 위 논리를 정확하게 적용시킬 수 있다.
\(S\)의 원소 수를 정확하게 \(\lfloor\sqrt{0.5N}\rfloor\)라고 두자. 더 많은 원소를 가지는 집합을 굳이 구성할 필요는 없다. \(N\)에 대해, \(M=\lfloor\sqrt{0.5N}\rfloor\le 2^q\)를 만족시키는 가장 작은 양의 정수라고 하자. 그리고 이진수를 \(F=\mathbb{F}_{2^q}\)의 원소와 혼동시킬 것이다.
그러면 \(S\)의 원소는 \(\{x\oplus(2^qi+i^3)\mid 0\le i<M\}\) 꼴로 구성이 가능하다. 여기서 \(x\)는 임의의 \(0\)이 아닌 작은 정수로 둔다. 가장 모범적인 것은 1이다. 또한 여기서 \(+\)는 정수 간의 덧셈이고, \(i^3\)는 \(i\)를 \(F\)에서 세제곱한 값이다. 이렇게 두면 \(i^3<2^q\)이기 때문에 \(i\ne j\)이면 \(2^qi+i^3\ne 2^qj+j^3\)이다.
또한 \(S\)의 모든 원소가 \(N\) 이하의 정수라는 것은 \(2^qi+i^3\le 2^q(M-1)+(M-1) < M2^q < 2M^2 \le N\)이므로 성립한다. 즉, 이 애드혹적인 발상과 \(\mathbb{F}_{2^q}\) 상의 곱셈을 구현하는 것으로 18762번 문제에서 요구하는 집합을 구성할 수 있다는 것이다.
P.S. 왜 굳이 제곱이 아니라 세제곱을 썼냐면, characteristic \(2\)에서는 \(a^2+b^2=(a+b)^2\)이기 때문...
이로서 18762번의 풀이를 마친다.