티스토리 뷰
1번:
티어:Silver 4
최근 5년 전국본선에 나왔던 고등부 문제 중 가장 쉬운 문제라 생각됩니다.
풀이는 뒤에서부터 생각하면 쉽게 나오는데, 도착 지점에서의 속력은 0으로 고정되어 있으므로, 도착 직전 지점의 속도는 최대 1이 됩니다. 이런 식으로 왼쪽으로 가면서 속도를 1씩 올리다가, 속도 제한에 걸리는 경우만 속도를 제한에 딱 맞게 조절해주면 됩니다.
2번:
티어:Platinum 2
고등부 2번은 반대로 어려운 문제입니다. 2번 문제부터 풀기 어려워지는 경향이 커지기 때문에, 부분점수를 긁는 연습을 열심히 하면 동상에 도움이 될 수 있습니다.
부분문제 1:x,y,z의 쌍은 O(N^3)개가 있으며, 각 쌍에서 답을 체크하기 위해서는 포함되는 S의 원소들이 포함되었는지 아닌지를 완점 탐색으로 체크하면 됩니다. 시간 복잡도는 O(N^3~N^4*2^N)입니다.
부분문제 2:가장 큰 지그재그 수열은 그리디하게 구할 수 있습니다. 현재 지그재그 수열이 t라 하면, t에 현재 원소를 넣을 수 있으면 추가하고, 아니면 t의 마지막 원소를 현재 원소로 대체하면 됩니다. 시간 복잡도는 O(N^4)입니다.
부분문제 3:x, y를 고정하고, 현재 i번째 원소까지 봤으면 f(x,y,i)를 결정해주면 됩니다. 시간 복잡도는 O(N^3)입니다.
부분문제 4:x가 고정되었을 때 여러 개의 f(x,y,z)를 동시에 찾을 수는 없을까요? f 함수는 C의 길이- 증가하는 길이 3 수열 개수 - 감소하는 길이 3 수열 개수로 표현할 수 있습니다. x 이하만 모은 배열을 B라 합시다. 위치가 i에 있는 B의 원소는 답을 i*(N+1-i)만큼 증가시킵니다. 이제 x가 증가하는 길이 3 수열의 중간 원소가 될 수 있는지를 체크하고, 가능하다면 왼쪽 원소 위치*(N+1-오른쪽 원소 위치)만큼 답을 빼줍니다. 감소하는 길이 3 수열에 대해서도 똑같이 해줍니다. 시간 복잡도는 O(N^2)입니다.
부분문제 5:한 원소가 추가될 때 영향을 받을 원소는 근처 3개 정도입니다. 이를 set 등으로 빠르게 찾아주고 업데이트하면 O(NlogN) 정도에 풀 수 있습니다.
3번:
티어:Platinum 2
2번과 3번의 난이도는 비슷하고, 저는 개인적으로 3번이 더 쉽다고 느꼈습니다.
전체 트리에서 최대로 넣을 수 있는 개미의 개수는 dp를 통해 구할 수 있습니다. dp[i][0]은 i번 노드에 개미가 없을 때, dp[i][1]은 i번 노드에 개미가 있을 때라고 정의합니다.
dp[i][1]=dp[i의 자손][0]+1이고, dp[i][0]=max(dp[i의 자손][0],dp[i의 자손][1])의 합입니다.. 답은 max(dp[i][0], dp[i][1])이 됩니다.
이 정보들을 통해서 dpp[i][0], dpp[i][1]=i번 노드에 개미가 없거나 있을 때 i번 노드의 자손들을 제외하고 최대로 들어갈 수 있는 값을 구해줄 수 있습니다.
이러면 i번 노드에 개미가 있거나 없을 때 들어갈 수 있는 최대의 개미 수를 구할 수 있고, i번 노드에 개미가 없어도 되는 곳들을 구할 수 있습니다.
개미가 있어야만 하는 곳을 연결해야지 문제가 되므로, 답은 쉽게 나옵니다.
4번:
티어:Diamond 3
제가 대회 중에 못 푼 문제입니다. 이 문제의 55점을 긁지 않고 전체 풀이만 생각한 것이 패인이라 생각됩니다.
Q<=10:쿼리 개수가 작으므로, 쿼리 없이 문제를 풀면 됩니다. dp[i][j]=i번째 원소가 j로 정해졌을 때 최소 연산 횟수라 정의하면 쉽게 문제를 풀 수 있습니다.
문자 개수가 5개 이하:쿼리가 많으므로 세그먼트 트리를 관리해 줍니다. 세그먼트 트리에는 2차원 배열을 저장해 주는데
dp[i][j]는 시작에 i번 문자, 끝에 j번 문자일 때 최소 연산 수이고, 이를 잘 관리해주면 됩니다. merge 연산이 오래 걸리기 때문에, 상수 최적화가 필요할 수도 있습니다
문자 개수가 많을 때: 문제를 문자가 2개일 때 케이스 여러 개로 쪼갤 수 있다는 관찰이 필요합니다. 문자가 2개일 때 케이스의 정답은 앞에서 A다가 그 다음부터 B인 경우밖에 없습니다. 케이스 여러 개는 기준 문자를 잡고, 기준 문자 이하면 A, 초과면 B로 나누면 됩니다. 이 케이스들의 최적 점은 증가하기 때문에, A와 B 사이를 넘는 경우, B와 C 사이를 넘는 경우 ...... 등으로 나눠지고, 이를 모두 더하면 원 문제의 답이 됩니다.