PS 일지 (5)

마지막 수정 시각: 2023-02-06 12:02:58

BOJ 27233

대회에서 한참 시간 쓰고도 못 풀었던 문제. 이런 류의 애드혹 / 컨스트럭티브에 정말 약한데 어떤 식으로 연습해야할지 잘 모르겠다.

일단 문제를 정렬로 생각하는 것에서 시작한다. 주어진 입력의 inverse를 만든다음 그 inverse를 정렬한다고 생각하면 동일한 문제가 되고, 이게 더 생각하기 편하다.

이 상태에서, 주어진 연산으로 무엇을 할 수 있는지 생각해보자. 맨 앞에 어떤 원소 \(x\)가 있을 때, \(x\)의 앞에 \(x-1\)을 붙여주는 건 다음과 같은 방식으로 할 수 있다.

\(x,\dots,x-1,y,\dots\) 에서, \(x-1\)의 앞 뒤를 잘라서 연산을 수행한다. 그러면 \(y,\dots,x-1,x,\dots\) 로 수열이 바뀌고 \(x\)와 \(x-1\)은 서로 연속해서 붙어있으므로 이 두를 하나의 수로 합쳐서 생각할 수 있다. 반대로 맨 끝 위치에서 \(x+1\)을 붙이는 것도 동일한 방식으로 수행할 수 있다.

이렇게 생각하면, \(N-1\)번의 연산으로 주어진 모든 수를 하나로 합칠 수 있으므로(정렬된 상태로 만들 수 있으므로) 문제를 해결할 수 있다. 라고 생각할 수 있으나, 실제로는 아니다.

만약 수열의 맨 처음 수가 \(1\)이고 맨 끝 위치가 \(N\)이면 \(x-1\)과 \(x+1\)이 존재하지 않아 이 방법을 쓸 수 없다. \(1\)과 \(N\)을 연결되어 있다고 생각하면 여전히 이런 방법을 쓸 수 있으나, 이렇게 할 경우 전부 합치고 나서 첫 수가 \(1\)이라는 보장이 없으므로 최대 전체 \(N\)번의 연산이 필요하게 된다.

첫 수가 \(1\)이고 끝 수가 \(N\)일 때의 해결법을 생각해보자. 이 상태에서 한 스텝만에 두 수를 합칠 수는 없으므로, 두 스텝만에 세 수를 합치는 것을 목표로 한다.

현재 상태가 \(1,\dots, 3, \dots, N\) 라고 하자. 1의 오른쪽, 3의 왼쪽에서 잘라서 연산을 수행하면, 수열은 \(3, \dots, N, \dots, 1\) 이 된다. 이 상태에서 3앞에 2를 붙이는 경우를 생각해보자.

중간 어느 위치에 2가 있든, 다음 스텝에서 2를 좌우로 잘라서 양쪽을 바꿔주면 \(1,2,3\)이 전부 연속하게 된다. 따라서 두 스텝만에 세 수를 연속하게 하나로 합쳐주었으므로 이러한 경우에도 항상 조건을 만족하면서 정렬을 할 수 있다. 이 방법을 그대로 구현하면 \(N-1\)번 만에 전체를 정렬할 수 있다.

BOJ 27234

Hello BOJ 업솔빙을 이어서 했다. 풀고 보니 C보다 훨씬 쉬워서 대회때 그냥 C 버리고 D 잡을걸 싶은 생각이 들었다.

\(DP(f, u) \) 를 1층에 \(f\)개의 컵을 쌓고 2층 이후에 \(u\)개의 컵을 쌓는 경우의 수라고 하자. 일단 답은 \(DP(1, n - 1) + DP(2, n - 2) + \dots + DP(n, 0)\) 이라는 것을 알 수 있다.

이제 \(DP(f, u)\)에 대해서, 2층에 \(f_2\)개를 쌓고 그 \(f_2\)개 위에 \(u_2\)개를 쌓는 경우를 생각해보자. 이 때 경우의 수는 \(DP(f_2, u_2) * DP(f - f_2 - 1, u - f_2 - u_2) * down(f_2+1)\)이 된다. 이 때, \(down(x)\) 는 위에 \(x-1\)개의 컵을 쌓을 수 있는 1층 경우의 수이다. 그리고 적당히 계산해보면 이 함수는 피보나치 함수랑 동일하다는 것을 알 수 있다.

가능한 모든 \(f_2, u_2\)에 대해서 저 식을 계산해서 더해주면 \(DP(f,u)\)도 계산이 된다. 따라서 전체 시간 복잡도 \(O(N^4)\)에 문제를 해결할 수 있다. \(N\) 제한이 150이어서 안 돌 것만 같은 기분이 들지만 제출해보면 상당히 빠르게 돈다. \(f_2, u_2\)를 가져갈 수 있는 경우의 수가 그렇게 많지 않아 실질적인 상수가 작기 때문이다. 넉넉하게 잡아도 많아야 \(N^2 / 4\)가 되는데, 이걸 기준으로 생각해보면 \(75 * 75 * 150 * 150 = 126,562,500 \) 이므로 단순 셈법으로도 시간 안에 돌아갈만하다고 생각할 수 있다.

BOJ 24044

올해 첫 다이아몬드 문제. 내가 좋아하는 스타일의 구성적 문제였다.

일단, 전체 그래프를 위상정렬하고 시작하자. \(cnt_i\)를 \(1\)번 정점에서 시작해서 \(i\)번 정점에 도달하는 경우의 수라고 정의하면, \(cnt\) 값은 쉽게 계산할 수 있다.

이제 여기서 적절한 정점 셋 \(b_1, b_2, b_3, \dots, b_x\) 를 정해서, 이 셋에서 항상 \(2 \cdot b_i \le b_{i+1}\)이 성립하게 만들어줄 것이다.

\(b_1 = 1\)로 놓고, 위상정렬한 그래프에서 정점들을 순차적으로 보면서 마지막 \(2 \cdot b_x \) 보다 현재 보고 있는 정점 \(i\)의 \(cnt\) 값이 작다면, 정점 \(b_x\) 에서 \(i\)로 가는 간선을 만들어준다. \(i\)가 \(b_x\)이상이면 1개, 아니면 2개를 연결해주어야 한다. 이렇게 되면 어느 경우에도, \(b_i\)는 \(b{i-1}\)의 2배 이상 3배 이하를 만족하게 된다. 또 이런 페이스로 커지면 앞의 모든 정점의 \(b_1\)부터 \(b_i\)까지의 모든 \(cnt\)값을 합한게 \(b_{i+1}\)보다 작을 수 밖에 없다. 비슷하게, 앞의 모든 정점과 간선이 다 연결된 정점이어도 마지막 \(b_x\)의 세배보다 더 클 수는 없으므로 항상 이런 논리로 위상정렬한 정점들의 맨 앞에서부터 순서대로 \(b\) 집합을 만들어 줄 수 있다. 이런 \(b\) 집합의 크기는 \(k\) 제한상 많아야 30개 정도이고, 이 모두와 간선을 만들어주는데에는 최대 60개의 간선이 필요하다.

이렇게 비트를 만들어주고 나면 1개의 간선을 써서 \(k\)를 절반으로 줄이거나, 2개의 간선을 써서 3분의 1로 줄이거나 두 가지 경우가 생긴다. 어느 경우에도, 많아야 3~40개의 간선이면 충분하므로 전체 120개 이하의 간선 조건을 넉넉하게 만족하면서 문제를 해결할 수 있다.

Prompt412 Round 181

7/8 풀었다. H는 비슷한 유형을 본적이 있는데 생각을 못 했다. 잘 집중해서 풀었으면 풀었을 거 같은데 영 집중력이 떨어져서...

C. BOJ 14246

투 포인터로 해결할 수 있다. 어떤 \(l\) 위치에 대해 \(l\)에서 \(r\)번 원소까지 다 더한게 \(k\) 이하인 제일 큰 \(r\)을 구한다. 이 \(l\)에 대해 문제의 조건을 만족하는 경우의 수는 \(n-r\)가지.

이제 \(l+1\)번 포인터에 대해, 여기에 대응되는 \(r\)포인터는 반드시 \(l\)포인터에 대응되는 \(r\)보다 더 오른쪽에 있다. 따라서 이전에 구해둔 \(r\)에서부터 이어서 계산하면 되므로 전체 시간복잡도 \(O(N)\)에 문제를 해결할 수 있다.

D. BOJ 1897

각 문자열을 하나의 정점으로 보고, 그 문자열과 정확히 한 글자 차이나는 다른 문자열들 간에 간선을 이어서 그래프를 만들자. 이 그래프에서 시작 문자열로부터 도달가능한 가장 길이가 긴 문자열이 답이 된다. \(O(kD^2)\)(\(k\)는 가능한 문자열 최대길이) 정도 시간에 해결 가능.

E. BOJ 9326

주어진 수를 소인수분해하자. 여기서 각 소인수 \(p^k\) 꼴에 대해, \(k\)를 \(2^0, 2^1, 2^2, \dots, 2^n\) 들의 합으로 표현하자(그러니까, 이진수로 표현하자). 여기서 나온 비트들을 이용해 \(p^{2^i}\) 꼴로 \(p\)를 분할해서 출력하면 그게 곧 답이 된다.

F. BOJ 20293

\(DP(x)\)를 \(x\)번 위치에서 마지막에 도달하기 위해 충전해야 하는 연료의 양 이라고 정의하자. 그러면 갈 수 있는 어떤 다음 위치들 \(v\)에 대해, \(DP(x)\)는 \(max(0, DP(v) - f_x + dist(x, v))\) 중 최솟값이 된다. 일단 \(v\)지점으로 이동하면 그 이후 \(DP(v)\)만큼을 충전해야 하고, 여기서 이 위치에서 충전 가능한 \(f_x\)만큼은 미리 충전을 해 둘 수 있기 때문이다. 이걸 그대로 구현하면 \(O(N^2)\)에 문제를 해결할 수 있다.

G. BOJ 10099

포탈은 무조건 현재 위치에서 두 개를 모두 설치해놓고, 둘 중 하나를 골라 거기로 들어가서 다른쪽에서 나오는게 최선이다. 따라서 이 경우만 고려한다.

이제 미리 각 위치에서 포탈을 쓸 수 있는 위치를 계산해둔 다음 다익스트라로 최단거리를 구해주면 \(O(RClog(RC))\) 시간에 문제를 해결할 수 있다.

Prompt412 Round 182

또 7/8 풀었다. G는 대회때 못 풀고 또 못 풀었다.. F가 너무 어려워서 시간이 오래 걸렸다. 항상 이런 유형에서 고생하는데 정말 어떻게 해야 잘 푸는지 모르겠다.

B. BOJ 12971

\(LCM(P_1, P_2, P_3)\) 이후부터는 똑같은 상황이 반복되므로, \(N\)을 저 값까지 순회하면서 조건 만족하는게 있는지 보면 된다. 이 값은 커야 \(300^3\) 이내이므로 충분히 빠르게 돈다.

C. BOJ 24500

처음에 문제를 잘못 읽어서 좀 헤맸다. 일단 \(N = 2^b - 1\) 꼴인 경우, 그냥 \(N\) 한장을 고르는게 최선이다. 그게 아니면 항상 2장으로 만들 수 있는데, 그냥 \(N\)과 \(N\) 이상의 가장 작은 \(X = 2^b - 1\) 에 대해 \(N\)과 \(X\)의 xor 값을 출력해주면 된다.

D. BOJ 25634

일단 켜진 전구의 전체 합을 구하고, 꺼진 전구는 음수값으로, 켜진 전구는 양수값으로 생각해서 연속 부분수열의 최소합을 구하자. 결국 합은 이 연속한 구간을 뒤집어서(반대 방향으로 더해서) 최대한 값을 크게 만들고 싶은 것이므로, 구해둔 합에 이 연속 부분수열의 최소합을 빼주면 그게 답이 된다. 연속 부분수열의 최소합은 DP로 \(O(N)\)에 구하는 방법이 잘 알려져 있으므로, 이 문제도 \(O(N)\)에 해결할 수 있다.

E. BOJ 13021

\(i\)번째 색칠을 배열에 \(i\) 값을 덮어씌우는걸로 생각하자. 결과 배열에서, 각각의 \(i\)에는 0 또는 1을 집어넣을 수 있다. 따라서, 모든 색칠을 마친 후 남아 있는 색깔의 개수를 \(c\)라고 할 때 답은 \(2^c\)가 된다. 제한이 작아서 전체 시간복잡도 \(O(NM)\)에 나이브하게 해결할 수 있다.

F. BOJ 19846

결국, 모든 구간의 길이는 짝수이며 항상 \(2N-2\) 이상이라는 점에 주목해보자. 배열을 aabbccdd..aabbcc.. 순서대로 계속 반복하게 만들어주면, 여기서 임의의 \(2N-2\) 이상 길이의 부분 문자열을 뽑았을 경우 항상 모든 문자가 등장하고 홀수 길이인 원소는 하나만 존재하게 된다. 따라서 이걸 그대로 출력하면 문제를 해결할 수 있다.

H. BOJ 8145

트리에서 일부 간선을 골라 값을 1 -> 0 으로 바꾸는 쿼리와 루트에서 \(x\)로 가는 경로의 길이 쿼리를 수행하는 문제이다. 온라인으로 해결할 경우 HLD를 이용해서 쿼리당 \(O(log^2N)\)에 문제를 해결할 수 있는데, \(N\) 제한이 좀 크고 시간이 빡빡해서 이렇게 하면 안 될 것 같다.

오프라인으로 문제를 바꿔서 생각해보자. 결국 어떤 \(x\) 쿼리 시점에 \(1\)번 노드부터 그 노드로 이어지는 간선중 몇개가 날아갔는지만 빨리 구하면 되는데, 각 정점마다 그 정점과 부모 정점이 끊어지는 시점을 기록해두면 dfs를 돌면서 세그먼트트리에 끊긴 시점에 1을 업데이트해주고, 쿼리할땐 쿼리 시점 \(x\) 이전에 몇개가 끊겼는지 계산해주면 \(O(logN)\)에 쿼리를 수행할 수 있다. 내 서브트리의 작업이 끝나면 다시 끊긴 시점을 0으로 돌려주면 된다. 따라서 전체 시간복잡도 \(O((N+M)logN)\) 정도에 문제를 해결할 수 있다.