링크

A (4:29 solve, +1 WA)

단순 반올림 문제이다. 근데 %.0lf 사용하면 틀린다. 이유는 잘 모르겠다.

B (9:05 solve)

두 수열이 같단 조건이 두 벡터가 같단 조건과 일치한다. 따라서 벡터를 set에 넣고 나중에 size 함수로 개수를 출력하면 풀린다.

C (21:02 solve)

각 무술을 배우기 전에 선행 되어야 할 무술들로 방향 간선을 연결하고, N번 정점에서 dfs를 돌려 reachable 한 정점들의 시간을 다 더하면 나온다. 순간 Disjoint Set을 사용하여 구현하다가 시간을 낭비했다.

D (32:05 solve)

문제 조건을 잘못읽어 (1,0), (-1,0), (0,1), (0,-1) 만 있으면 되는게 아닌가 착각했다. 하나의 벡터를 계속 이용해서 다른 점에 도착할 때까지 이동하므로, 필요한 것은 각 정점 쌍에 대하여 이동하는데 필요한 벡터를 구하고, 해당 벡터를 최대 공약수로 나누어 성분이 서로소인 관계로 만든다. 이후 해당 값들을 set을 이용하여 중복없이 세주면 된다.

E (65:26 solve)

각 점에서 out degree가 1이 되도록 그래프를 만들 수 있는지 묻는 문제이다. 가능한 경우를 잘 생각해보면 각 컴포넌트 별로 정점의 개수와 간선의 개수가 같아야만 한다. 주어진 그래프에서 컴포넌트의 개수를 $k$ 라고 하면 정답은 $2^k\pmod{998244353}$ 이다. 본인은 가능한 경우를 그래프에서 리프들을 뜯어내는 식으로 확인해서 구현에 시간이 꽤 걸렸다.

F (upsolving)

끝나고 1분뒤에 맞았다. 우선 임의의 순열에 대하여 점수가 어떤식으로 계산되는지 살펴봐야 한다. 사이클의 길이가 각각 $g_1, g_2, \cdots{}, g_k$ 라고 하면, 해당 순열의 점수는 $\operatorname{lcm}(g_1, g_2, \cdots{}, g_k)$ 가 된다. 그 이유는 각 사이클이 원래대로 돌아오는데 각 사이클 길이만큼 걸리므로, 모두 다시 원점으로 돌아오기 위해서는 최소 공배수만큼 돌아야 된다. 이제 순열의 점수를 구했으니, 순열을 $k$ 개의 사이클로 분해하는 경우의 수를 잘 세면 문제가 풀릴 것이다.

문제를 읽어보면 $N$이 상당히 작다. 따라서 자연수의 분할을 그대로 구현해도 시간이 충분할 것이라 추측할 수 있다. 만약 $N=g_1+g_2+\cdots{}+g_k$ 로 분할하였다고 하면, 경우의 수는 아래와 같다. 또한 $g_1, g_2, \cdots{}, g_k$ 중 $i$ 가 몇번 나타나는 지를 $x_i$ 라고 하고, $S_i=g_1+g_2+\cdots{}+g_i, S_0=0$ 라고 하자.

\[\displaystyle {1 \over {x_1!x_2!\cdots{}x_N!} } \prod_{i=1}^{k} { {N-S_{i-1} \choose g_i}\times{(g_i-1)!} }\]

복잡해 보이지만 마지막 $(g_i-1)!$ 부분만 빼면 앞의 식은 사실 집합의 분할 경우의 수이다. 그렇다면 뒤의 $(g_i-1)!$ 의미는 각 집합별 사이클의 종류의 개수인데, 이 경우의 수는 자명히 원소가 $g_i$ 개인 원순열과 같다. 따라서 $(g_i-1)!$ 가 곱해지게 된다. 따라서 위 식에 $\operatorname{lcm}(g_1, g_2, \cdots{}, g_k)$ 을 곱한 결과물 들을 모두 더하면 답이 나온다. 이는 재귀 호출로 자연수의 분할을 구현 후, 전처리 된 팩토리얼과 그 역원들을 이용하여 빠르게 계산이 가능하다.

총평

전반적으로 실수가 많은 대회였다. 최근에 코포와 앳코더 모두 초반부 문제에서 구현 실수나 문제를 잘못 이해하는 등 실수가 잦은데, 이를 줄일 필요가 있어보인다. (좀 더 생각을 단순화하거나, 문제를 읽을 때 성급하게 읽지 않도록 하자.) 그래도 F번을 대충 35분 언저리에 푼 것은 그나마 이번 라운드에서 나은 점 같다. 어차피 앳코더는 매주 있으니 하나 하나에 큰 의미를 두지 않고 꾸준히 풀면 언젠가 대회 중 6솔브도 가능할 것이라고 생각한다.