AtCoder Beginner Contest 134 F - Permutation Oddness

어제는 AtCoder Beginner Contest를 했는데, E번까지 23분만에 순삭했음에도 불구하고 F를 못 풀어서 약간 존심이 상했다. 사실 ABC 마지막 문제는 Beginner Contest라는 이름에 맞지 않게 항상 난이도가 꽤나 높다.

F를 푼 사람이 53명이고, 나는 85등이니 상당히 선방한 셈이다.

문제는 아주 간단하다. n과 k가 주어지는데, 1~n까지의 숫자로 이루어진 순열 중, 순열의 oddness를 $\sum^{n}_{i=1}{|i-p[i]|}$로 정의했을 때, oddness가 k인 순열의 수를 구하는 문제이다.

oddness의 예시를 하나 들자면

n = 4일 때, 순열 4312의 oddness는 |1-4| + |2-3| + |3-1| + |4-2| = 8이다.

먼저 oddness는 항상 짝수라는 것은 쉽게 알 수 있는데, 임의의 순열은 인접한 두 원소를 swap하는 operation을 통해 만들어낼 수 있는데 이 operation을 수행할 때 oddness는 2가 감소하거나, 그대로이거나, 2가 증가하거나 두 가지 경우의 수밖에 없기 때문이다.

그 다음부터는 진전이 없다. 혹시나 하는 마음에 n마다 각 oddness의 순열 수를 출력해보았는데,

n=1: 1

n=2: 1 1

n=3: 1 2 3

n=4: 1 3 7 9 4

n=5: 1 4 12 24 35 24 20

...과 같은 불규칙이 이어졌다. 참고로 oddness는 앞에서부터 0, 2, 4, ...이다.

사실 이 순열은 이미 있는 순열이다. 구글에 저 순열을 그대로 검색하면 OEIS의 A062869가 나오는데, 저 설명과 똑같다.

사실 이 순열을 그대로 복사해다가 제출해도 당연히 풀린다. 문제를 이렇게 풀어도 할 말은 없다. cheating인지 아닌지 구분이 모호하긴 하지만.. 복붙한 사람도 문제를 푼 53명 중 최소 20명 이상 존재한다.

이 순열에 관한 논문도 존재한다.

https://arxiv.org/pdf/1202.4765.pdf

관심있는 사람은 심심할 때 한 번 읽어봐도 좋을 것이다. 나는 3페이지까지인가 읽다 말았다.

아무튼, 풀이는 (당연하지만) dp를 이용하는 것인데 방법이 상당히 흥미롭다.

다음과 같이 그림을 그려보자.

순열의 oddness는 가로 점선이 직선과 만나는 횟수의 합과 동일함은 자명하다.

이제 3차원 dp테이블을 만드는데, 다음을 의미한다.

dp[i][j][k] = i번째 점선까지, 연결되지 않은 것이 j개이고, 점선이 실선과 만나는 횟수가 2k인 조합의 수이다.

(정확히는 한쪽 사이드에 있는 연결되지 않은 노드)

예를 들어 아까 본 그림을 i=3까지만 그린다면 다음과 같다,

왼쪽의 2번, 오른쪽의 4번은 누군가랑은 이어지겠지만 아직은 이어지지 않았다.

이 상황은 i = 3, j = 1, k = 4인 상황이다.

이러한 상태에서 노드 한 쌍을 추가하면, 아래 4가지 경우가 발생한다.

i) 추가된 노드 둘이 연결되는 경우

이 경우 j는 유지되고, 실선과 만나는 횟수는 2j번 추가되니 dp[i + 1][j][k + j]가 된다.

ii) 둘 다 panding

이 경우 j가 하나 늘어나고, 실선과 만나는 횟수는 2(j + 1)번 추가되어 dp[i + 1][j + 1][k + j + 1]이 된다.

iii) 하나는 panding, 하나는 연결

이 경우 j는 그대로이고, 실선과 만나는 횟수는 2j번 추가되어 dp[i + 1][j][k + j]가 된다.

다음으로 이렇게 되는 조합의 수를 세야하는데, 하나는 panding되고 하나는 연결되려면

panding되는 것이 오른쪽/왼쪽인지, 어떤 노드와 연결되는지 두 가지가 있으므로 2j개의 경우가 있다.

iv) 둘 다 연결

이 경우 j가 하나 감소하고, 실선과 만나는 횟수는 2(j - 1)번 추가되어 dp[i + 1][j - 1][k + j - 1]이 된다.

마찬가지로, 이렇게 되는 조합의 수는 j * j개가 있다.

이 4가지를 케이스를 고려하며 dp테이블을 완성하면, dp[n][0][k / 2]가 우리가 원하는 답이다.

+) 다른 사람의 코드를 보다가 다음과 같이 쓸 수 있다는 것을 하나 배웠다.

a += 3;

a %= MOD;

를 해주어야 할 때

(a += 3) %= MOD;

과 같이 쓸 수 있다. 이는 +=과 같은 연산자는 오른쪽에 있는 값을 왼쪽의 레퍼런스에 더해준 뒤, 왼쪽의 레퍼런스를 그대로 반환해주기 때문이다.

MOD를 많이 해주어야 하는 ps에서 유용하게 사용할 수 있을 듯.

++) 이번 ABC에는 영어 editorial이 없어서 일본어 버전을 어렵게 해석해가며 풀이를 공부했는데, 일본 사람들은 그냥 읽으면 될 걸 고생해가며 읽는다니 뭔가 억울했다.

생각해보면 코포를 할 때도, ICPC에서도 죄다 영어라서 읽고 문제를 이해하는 시간이 더 걸려서 항상 그만큼 손해를 보고 있는 것 같다.

ps가 인재 양성에 도움이 된다는 전제 하에(내 경험상 코딩 뿐만 아니라 문제 해결력 향상에 엄청 많은 도움이 된다) 한국의 경쟁력 향상을 위해, 한국에도 코포처럼 대회를 주기적으로 여는 사이트가 생겼으면 (rating도 매기고) 하는 생각이 들었는데, 백준이 그런 역할을 할 수 있다면 참 좋을 것 같다.