Codeforces Round #479(Div. 3)

C. Less or Equal

쉽게 풀 수 있을 것이라고 생각했는데, 틀려서 고민 좀 했다.
틀린 이유는 입력 조건을 제대로 확인하지 않아서 였다. (0 <= k <= n) 라는 입력 조건때문에 k값으로 0이 들어올 수도 있다.
k값이 0인 경우를 처리해주지 않아서 틀렸고, 이를 처리하여 AC를 받았다.

D. Divid by three, multiply by two

입력으로 수열이 주어지면 이전 수에 3으로 나누거나(3으로 나누어 떨어질 때 가능), 2를 곱하는 연산 둘 중의 하나를 시행하여 다음 수가 나오도록 수열을 재배치 하는데, 정답이 있다는 것이 보장된다.
나는 각 수에서 시작해보는 백트래킹 같이 재귀를 이용해 풀었는데, 같이 푼 친구는 각 수에서 시작하여 그래프를 만들어 보는 식으로(*2, /3 연산 중에 다음 수가 그 배열에 존재하는 경우에만 그래프를 만든다) 했는데, 신기하게도 그렇게 하면 한줄의 그래프가 만들어지는 것 같다. 그렇다면 애초에 어떤 수 x가 있을 때, 2x와 x/3이 둘 다 그 수열에 존재하면, 답이 나올 수 없는건가?
생각해보니 그렇다. 좀 더 정확히 말하면 어떤 수 x가 있을 때 2x를 다음 수로 하면 x/3은 그 이후에 절대 나올 수 없고, 마찬가지로 x/3을 다음수로 하면 2x는 그 이후에 절대 나올 수 없다.
1) x -> 2x가 된 경우
일단 x/3이 가능하려면 x는 3을 인수로 갖는다. 그런데 2x가 되면 인수 2가 추가 되고, x/3이 나오려면 추가된 인수 2를 없애야 하는데, 크기를 줄이는 방법은 /3밖에 없으므로 결코 x/3이 될 수 없다.(결코 x/3과 같은 인수를 가진 수가 나올 수 없다.)
2) x -> x/3이 된 경우
x는 3을 인수로 가지고 있는데 x/3은 2x에 비해 인수 3이 하나 적어지게 된다. 그런데 크기를 늘리는 방법은 *2밖에 없으므로 결코 2x가 나올 수 없다.(2x와 같은 인수를 가진 수가 나올 수 없다.)

그리고 마지막으로 출제자의 공식 풀이를 봤는데...

수열의 각 수의 인수 3의 개수를 세서 인수 3의 개수가 많은 순(내림차순)으로, 인수 3의 개수가 같으면 수의 크기가 작은 순(오름차순)으로 정렬한 후에, 그대로 수를 출력해주면 답이 된다....

엄청 간단하다... 과연 저렇게 해도 되는걸까?
생각해보면, 답이 존재한다는 게 보장되므로, 일단 3을 인수로 가지는 수가 있을 때, 우리가 할 수 있는 연산은 *2, /3뿐이므로 그 수를 만들기 위해서는 먼저 3을 인수로 가지는 수가 필요하다. 만약 인수 3의 개수가 같은 경우는 작은 쪽에 *2를 해서 만들 수 있을 것이고 개수가 다른 경우는 큰 쪽에 /3을 해서 작은 쪽을 만들 수 있을 것이다.

즉, 인수 3의 개수가 다르면 *2를 사용할 수 없고(*2를 쓰려면 인수 3의 개수가 같은 수가 존재해야 한다) /3만 가능하므로 내림차순으로 정렬하고, 인수 3의 개수가 같은 경우는 *2밖에 안되므로 오름차순으로 정렬해주면 된다.


E. Cyclic Components

일반적인 사이클이 아닌 문제 조건에 맞는 사이클을 찾는 문제인데 일반 사이클 문제보다 아주 약간 더 까다로웠다. 방문하지 않은 점부터 dfs를 해서 시작 점과 직전 점을 같이 parameter로 보내서 직전 점으로는 가지 않고, 결국 시작 점으로 돌아오면 사이클인 것으로 판단했고, 중간에 한 정점에 연결된 간선이 2개가 아니면 커트했다. 이 문제에서의 사이클은 한 정점에 간선이 2개만 연결되어 있어야 한다.

근데 이 문제 역시 공식 풀이를 보니...
일반적인 dfs를 사용하면서 vector에 한 번 dfs할 때마다 방문한 정점을 모아놓고, 그 정점들이 모두 각각 간선을 2개씩 가지고 있는지 체크해서 모두 간선을 2개씩 가지고 있으면 사이클로 본다. 하나의 정점이라도 간선이 2개가 아니라면 문제에서 요구하는 사이클이 아닐텐데, 한 번에 방문할 수 있는 모든 정점이 간선을 2개씩 가지면 문제에서 요구하는 사이클일까?  직접 그려보고 해보니 정말 dfs로 한 번에 방문 가능하면서 간선이 2개이려면 그럴 수 밖에 없다... 공부 좀 더 해서 증명도 해봐야겠다.


F. Consecutive Subsequence

이 문제는 가장 긴 증가 부분 수열 문제와 비슷해 보이는데, 1씩 증가하는 부분 수열이어야 한다. 그래서 dp로 풀 경우 일반적인 가장 긴 증가 부분 수열은 O(n^2)이 걸리는 반면에, 이 문제는 dp로 O(n)만에 풀 수 있다.
d[n] = n을 마지막으로 하는 가장 긴 1씩 증가하는 부분 수열의 길이
d[n] = d[n - 1] + 1이 된다.

일반적인 가장 긴 증가 부분 수열은 n보다 작은 모든 값에 대해 살펴봐야 해서 O(n^2)이지만, 1씩 증가하는 경우는 n - 1에 대해서만 보면되니까 O(n)이다.

물론 가장 긴 증가 부분 수열의 경우 O(nlogn)에 푸는 풀이가 있긴한데, 그 풀이도 공부해 봐야겠다.

그리고 이 문제에서는 수가 매우 커서 map(혹은 좌표압축)을 이용해 dp배열을 구현해야 한다.