문제 : https://www.acmicpc.net/problem/13208 전에는 못 풀었는데 드디어 풀었다~ $state[a][b]$ : 조승현13이 $a$에 있고 조승현16이 $b$에 있는 상태 를 정점으로 하고 $c[a] * c[b]$를 정점의 비용으로 가지는 그래프를 생각해보자. 우리가 해야 할 것은 $state[a][b]$에서 $state[b][a]$로 가기 위해서 지나가는 정점들의 비용의 최대값을 최소화 하는 것이다. 만약에 문제가 정점의 비용을 최소화하는게 아니라 간선의 비용을 최소화하는 문제였다면 MST를 만들어서 구할 수 있을 것 같았다. 비슷한 아이디어로 정점의 비용이 작은 것부터 큰 것 순으로 보면서 트리를 만들어보기로 했다. 과정은 대략 다음과 같다 1. 정점을 비용순으로 정렬하고 비용이 작은 것 부터 본다. 2. 현재 보고 있는 정점이 $u$라고 하자 3. $u$와 인접한 정점들을 본다. 인접한 정점은 $v$라고 하자. 4. 만약 $u$와 $v$가 다른 집합에 속하는데 $v$의 비용이 $u$의 비용보다 작거나 같다면 $u$와 $v$를 같은 집합으로 합친다. 그리고 간선$(u, v)$를 따로 저장한다. 위 과정을 반복해서 나오는 간선들을 모으면 트리가 된다. 또한 이 트리상의 경로로만 이동하면 문제에서 요구하는 답을 찾을 수 있다. 직관적으로 이해할 수 있으므로 증명은 생략한다. 이제 문제는 트리에서 두 정점을 연결하는 경로상에 있는 정점의 비용 중 최대값을 찾는 문제로 바뀐다. 이건 LCA 를 이용하면 각 쿼리를 $O(lgN)$에 처리할 수 있다. 문제를 푸는 총 시간 복잡도는 시간 복잡도는 아마 $O(N(N+M)+QlgN)$이 될 것 같다. (먼저 맞은 사람들 코드를 보니깐 더 빠른 방법이 있나 보다.) 코드 : http://ideone.com/eBn2sQ
문제 : https://www.acmicpc.net/problem/1034 램프에 $K$번의 조작을 다 하고 나서 최종적으로 몇 개의 행의 불이 완전히 켜져있다고 생각해보자. 불이 완전히 켜져있는 행들은 초기에 서로 켜져있는 불의 상태가 완전히 같았어야한다. 왜냐하면 램프에 가해지는 조작은 열 단위로 가해지기 때문이다. 위 사실을 알고나면, 문제를 이렇게 생각할 수 있다. $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는가? 만약에 켤 수 있다면 그 행과 똑같이 생긴 행의 수를 답으로 고려해 볼 수 있고, 최종 답은 그러한 행의 수 중 최대가 된다. 이제 $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는지를 알 수 있으면 되는데, 이는 처음에 꺼져있는 열의 수보다 $K$가 크거나 같을 때 홀짝만 잘 따지면 알 수 있다. 코드 : http://ideone.com/tcrFIU
댓글
댓글 쓰기