티스토리 뷰

코드포스 GYM 링크


A. Avoiding the Apocalypse


내가 아직 풀지 않았다.


코드 보기


B. Button Bashing


$n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다.


코드 보기


C. Citadel Construction


2차원 좌표 평면에 $n$개의 점이 있을 때, $n$개의 점을 통해 만들 수 있는 삼각형, 사각형 중 최대 넓이를 구하는 문제다.

2013 대전 리저널 D번 문제와 똑같지만 $n \leq 1000$으로 제한이 작다. 우선 Graham-Scan으로 $O(N \lg N)$만에 Convex-Hull을 구한다. 답이 되는 점들은 Convex-Hull을 이루는 점들 중에 있음이 자명하다.

최대 넓이를 구하기 위한 $O(N^2)$ 방법으로는 점 $i$를 잡고 점 $j$를 반시계방향 순서대로 진행했을 때, 직선 $\overline{ij}$ 에서 양 면으로 가장 먼 점 두 개를 잡아 사각형의 면적을 구하면 된다. 이 때 $j$가 반시계방향으로 이동함에 따라, 양 면에서 가장 먼 두 점 또한 반시계 방향으로 이동하게 되므로 $O(N^2)$ 시간안에 계산할 수 있다. 이러한 작업을 rotating-calipers 라고 부른다.


코드 보기


D. Dropping Directions


사거리가 $N$개 있고, 그 중 한 사거리가 도착점으로 주어진다. 사거리 사이에서 이동 규칙이 있을 때, 최소 개수의 이정표를 세워 도착점으로 도달하게 하는 문제다.

들어오는 방향을 기준으로 하나의 사거리를 4개의 정점으로 분리할 수 있다. 이 정점들은 in degree가 1이고, out degree 또한 1이며, 하나의 고리 형태를 구성한다. 이 고리들 중 도착점을 포함하지 않은 고리의 개수가 정답이다.


코드 보기


E. Excellent Engineers


$n$명의 사람이 있고 세 분야에 대해서 등수를 매겼다. 세 분야 모두 자신보다 앞선 사람이 없는 사람의 수를 구하는 문제다.

우선 첫 분야를 기준으로 정렬한다. 그러면 이제 정렬되지 않은 두 분야 문제로 바뀐다. 이는 두 번째 분야 등수를 indexed tree의 index로 삼고, 세 번째 분야 등수를 value로 삼아서 index tree를 돌리면 해결할 수 있다.


코드 보기


F. Floating Formation


그래프에 $n$개의 정점이 있고, $m$개의 간선이 있다. 차수가 1인 노드는 없어진다. 새로 차수가 1인 노드가 생기면 그 노드 또한 없어진다. 배를 정점에 연결하면 정점의 차수가 늘어나 정점이 없어지는 것을 방지할 수 있다. $k$개의 배를 사용할 수 있을 때, 가라 앉는 정점의 개수를 최소화하는 문제다.

그래프가 주어졌을 때, 싸이클에 포함되어 있는 정점은 없어지지 않는다. BCC(Biconnected Component)를 통해 그러한 정점들을 구할 수 있다. 문제 조건에 따라 초기 상태에서 없어지지 않는 정점이 존재한다. 없어지지 않는 정점들 중 하나를 트리의 루트로 삼는 BCC를 구한다. 싸이클에 포함되어 있는 정점들을 색칠하고, 그 정점들의 조상 정점들을 모두 색칠한다. 이 때 색칠된 정점들이 최종적으로 없어지지 않는 정점들이 된다.

이제 $k$개의 배를 적절히 사용하여 없어지지 않는 정점들의 개수를 최대화 해야한다. 이는 트리에서 말단 정점들을 선택하여 조상까지 모두 색칠할 때 최대로 색칠하는 문제이며, KOI 2013년 고등부 4번 수족관3 문제에서 사용한 욕심쟁이 기법으로 해결할 수 있다. 그 욕심쟁이기법은 매순간 최대로 색칠할 수 있는 정점이 많은 말단 정점들 순서대로 색칠하는 방법이다.


코드 보기


G. Growling Gears


$n$개의 기어가 주어지고, RPM에 따른 토크가 기울기가 음수인 포물선으로 주어진다. 최대의 토크를 낼 수 있는 기어 번호를 출력하는 문제다.

포물선이 $-aR^2 + bR + c$로 주어지면, 낼 수 있는 최대 토크는 $c + \frac{b^2}{4a}$다. 분수 비교를 통해 이 값들 중 최대값을 구할 수 있다.


코드 보기


H. Highway Hassle


$n$개의 정점이 있고, $m$개의 간선이 있다. $n$개의 정점 중 $s$개의 주유소가 있다. 연료통의 최대 용량은 $t$이며, 주유소 별로 주유 가격이 다를 수 있다. 간선을 지날 때 기름이 닳고 이동 도중 기름이 바닥나면 안된다. 시작점과 도착점이 주어질 때, 시작점에서 도착점으로 가는 최소 주유 비용을 구하는 문제다.

주유소의 개수 $s$의 제한이 $s \leq 120$으로 굉장히 작다. 주유소 사이의 최단 거리를 구하는 것은 Dijkstra 알고리즘을 $s$번 수행하여 구할 수 있다. 주유소 $u$에서 다른 주유소 $v$로 최단 거리로 이동할 때 반드시 아래에 주어진 두 가지 경우 중 하나다.


  1. 주유소 $u$에서 기름을 꽉 채워서 가는 경우
  2. 주유소 $v$에 도착했을 때 기름이 바닥나는 경우


이에 따라 주유소 별로 주유소에 도착햇을 때 기름이 남은 가능한 경우는 총 $s^2$가지 경우 뿐이다. 이에 대해 Dijkstra 알고리즘을 하면 총 시간복잡도는 $O(s^3 + s(m + n \lg n))$이 된다.



코드 보기


I. Interesting Integers


내가 아직 풀지 않았다.


코드 보기


J. Jury Jeopardy


특정 조건을 만족하는 미로가 있고, 그 미로를 돌아다니는 로봇이 이동하는 규칙이 있다. 로봇이 미로를 이동하는 방식이 주어졌을 때, 미로를 구하는 문제다.

미로의 모든 부분을 '#'로 채우고 로봇이 이동하는 곳을 '.'로 바꾸면 된다. 시작점이 어디인지 잘 모를 수 있으므로, 상대적으로 큰 미로판에서 일부 부분만을 출력하면 된다.


코드 보기


K. Key to Knowledge


OX 퀴즈에 $m$개의 문제가 있고, $n$명의 응시자가 제출한 답안과 맞은 문제 수가 주어졌을 때, 실제 시험에서 가능한 정답지의 가지수를 구하는 문제다.

$m \leq 30$으로 $m$ 제한이 큰 편이다. 정답지 후보의 개수는 $2^m$으로 상당히 크다. 이제 문제를 왼쪽과 오른쪽 두 부분으로 나눈다. 그러면 각 문제 집합 별로 가능한 정답지 후보의 개수는 많아야 $2^{15} = 32768$가지가 된다. 이제 반으로 나눈 정답지 후보 두 개를 적절히 합쳐 실제 가능한 정답지가 되는지 확인하면 된다.


코드 보기



댓글
댓글쓰기 폼