kjk9704   11달 전

이 문제는 각 index의 flip 수가 균형 있게 분배하는 것이 중요한 문제입니다.

n=1인 경우 0, 1 뿐이며 이 때 flip index는 0, 0입니다.

n=2인 경우 00, 01, 11, 10이며 이 때 flip index는 1, 0, 1, 0입니다.

n=3인 경우 000, 010, 011, 111, 110, 100, 101, 001이며 flip index는 순서대로 "12021202"입니다.

이런 원리를 적용해서 n=5까지 확대하면 flip index는 "43424341434043121030124210302120"가 됩니다.

잘 보시면 flip index 0은 6개, 1은 6개, 2는 6개, 3은 6개, 4는 8개가 있습니다.

다 더하면 6+6+6+6+8=32이고 최대 수와 최소 수의 차이는 2 이하이므로 문제 조건을 만족합니다.

(문제 조건 : For any i ≠ j values c_i and c_j have to differ by no more than 2)

--------------------------------------------------------------------------------------------------------------------

그러면 임의의 n에 대하여 c_i의 리스트는 어떻게 될까요?

우선 n=12라고 가정합니다.

그 다음 2 * (int(math.floor(2 ** 12 / 12 / 2))) = 340이 됩니다.

그러면 c_i 리스트는 [340, 340, 340, 340, 340, 340, 340, 340, 340, 340, 340, 340]이 됩니다.

그 다음 (2^12 - 12 * 340) / 2 = 8이 되며 이것은 340 8개를 +2 해서 342로 변환하라는 의미입니다.

즉, {340, 340, 340, 340, 342, 342, 342, 342, 342, 342, 342, 342}가 되며 이것은 유일한 멀티셋입니다.

같은 원리로 n=17까지 멀티셋을 구해서 오프라인 환경에서 flip index를 미리 구하고 하드 코딩해서 제출하는 방법이 존재합니다.

-------------------------------------------------------------------------------------------------------------------------------------------------

추신 : 이 문제 증명이 매우 어렵습니다.

저번에 해결했던 소방차게임은 구현이 어려웠지 증명은 비교적 쉬운 편이였는데 이 문제는 증명도 더럽게 어렵고 구현 과정도 일반적이지 않는 것에서 solved ac 티어를 어떻게 측정해야 하는지 잘 모르겠습니다.

그리고 이 문제는 2021-2022 Russia Team Open, High School Programming Contest B번 문제이며 대회 당시 아무도 해결하지 못 한 전적을 가지고 있습니다.

추가로 "모든 자연수 n에 대하여 균형 있는 그레이 코드는 존재한다"는 논문이 존재합니다.

View of Balanced Gray Codes

Balancing Cyclic $R$-ary Gray Codes$\,$ II

위키백과에 찾아보시면 Balanced Gray code 항목에 존재합니다.

Gray code - Wikipedia

그리고 놀랍게도 에디토리얼이 존재합니다.

제가 할 수 있는 것은 여기까지인 것 같습니다.

나머지는 저보다 똑똑한 분들이 이 문제를 잘 해결해줄 것이라고 믿고 있습니다.

kjk9704   11달 전

논문에서 mock 데이터를 추출하여 수작업으로 일부분 수정했습니다.

n=1, n=5까지의 mock 데이터입니다.

이 mock 데이터들을 통해 n=17까지 유효성 검사 모두 통과하면 AC 판정 받을 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.