problem solving 20160828-1

옛날부터 모아오던 문제집인데 이제서야 정리... 대부분 IOI 합숙교육때 봤던 문제들이다.

koistudy 1534. 369 마스터

http://koistudy.net/?mid=prob_page&NO=1534

수의 개수가 10^8개이다. 단순한 알고리즘으로는 10^8 * lg(10^8) / lg(10) 정도라 아마 TLE가 날 것이다. 하지만 루프가 단순하면 10^8 정도는 무난하게 돌릴 수 있을 테니, 각각의 숫자를 아주 빠르게 판별할 수 있으면 괜찮다.

여기서 약간의 전처리를 통해서 판별을 아주 빠르게 할 수 있는데, 100000 미만의 i에 대해서, 해당 수가 369 수인지를 전처리 해두면, 10^10 크기의 수 X는, X / 10^5가 369 수거나 X % 10^5가 369 수이면 369 수이다. 이를 통해서 전처리 후 O(E-S)에 풀 수 있다.

koistudy 1564. 괄호 매칭 2

http://koistudy.net/?mid=prob_page&NO=1564

O(N^2)는 쉬우니 O(N) 알고리즘에 주목해보자. 각각의 끝점 괄호에 대해서 시작점으로 올 수 있는 괄호의 수를 DP로 빠르게 구할 수 있다. 만약에 끝점에 대응되는 시작점 괄호를 찾지 못했다면, 시작점으로 올 수 있는 괄호는 자명히 없다. 찾았을 경우, DP[i] = DP[i에 매칭된 시작점 - 1] + 1 이다. DP 배열의 합이 답이 된다.

BOI 2009. Candy Machine

https://www.acmicpc.net/problem/3350

x축을 수레의 위치, y축을 시간이라고 두고 모든 점들을 찍어보자. 이 때 수레 하나의 움직임은

 * y좌표가 증가하는 방향으로 움직이며 (시간을 거스를 수 없으니까)

 * y축과 방향이 45도 이하이다 (속도가 1 이하니까)

라는 특징을 가진다.

x축 y축을 잊고, x+y / y-x축에 대해서 생각해 보면, 수레는 x+y, y-x 모두 monotonically increasing하는 형태를 띈다. 즉. 점들이 있을 때, x / y 모두 monotonically increasing한 최소의 체인으로 점을 모두 덮는 문제로 환원할 수 있다. 이는 그리디하게 LIS를 구하는 방식과 유사하게 풀 수 있다.

HDU 5361. In Touch

http://www.nowcoder.com/questionTerminal/959e87cf7ce8490a88bce73d4eb94432

저지 사이트가 글을 쓰려고 하니까 죽어있는데... 아깝게 됐다.

dijkstra algorithm을 그냥 사용하면 N^2니 문제를 풀기에는 부족하다. 여기서 상당히 좋은 아이디어가 있는데, 끝점으로 가는 데 teleport 비용을 지불하지 말고, 시작점에서 teleport 비용을 일단 지불하고 나중에 생각한다고 해보자. 이렇게 되면, 간선에는 가중치를 부여할 필요가 없고, 정점에 Ci의 가중치가 붙는 꼴이 되며, 답은 Dist(i) - C(i)가 된다.

이제 다익스트라 알고리즘을 돌린다. Dist(i) + C(i)가 증가하는 순으로 priority_queue를 관리해주면, 한번 갱신해 준 노드를 다시 갱신할 필요가 없어서, std::set 등의 자료구조를 동반해서 O(NlgN)에 최단 경로를 계산할 수 있다.

ACM Phuket 2015. Terrorists

https://www.acmicpc.net/problem/11786

임의의 spanning tree를 잡고 경로가 전부 spanning tree 상에 속한다고 생각해 보자. 이 때는 LCA를 O(lgN)에 계산하는 방법으로 쉽게 문제를 해결할 수 있다.

하지만, 경로가 spanning tree상에 속하지 않을 경우가 존재할 것이다. 이 때는 spanning tree에 없는 임의의 에지를 사용할 것이다. 고로, 쿼리 S, E에 대해서 해당 에지를 거치는 최단 경로를 구할 수 있으면 된다. 다행이도 그러한 에지는 많아야 50개라 이를 미리 전처리 해두면 최단 경로를 계산할 수 있다.

World Finals 2012. Infiltration

https://www.acmicpc.net/problem/4207

문제에서 주어지는 그래프는 tournament graph라는 독특한 형태의 그래프이다. 이 그래프에서는 모든 정점에 대해서 indeg(i) + outdeg(i) == n-1인데, Sigma(indeg(i) - outdeg(i)) = 0이기 때문에, outdeg(i) >= (n - 1) / 2 인 점 i가 무조건 존재한다. 이러한 점을 하나 잡으면 남는 그래프 역시 tournament graph이기 때문에 이 짓을 반복하면 O(lgN) 정도 크기의 해를 항상 찾을 수 있다. 저게 계산하면 아마 6이었던 거 같다.

물론 이게 최적이라는 보장은 없기 때문에, 5 이하의 해가 없는지를 찾아야 하며, 이는 조합 탐색으로 가능하다. bitmask를 써야 빠르게 작동해서 조금 귀찮다. (n <= 64 주지 ㅠㅠ)

Coder's high 2016. 이진 탐색

https://www.acmicpc.net/problem/13121

전체 수열에 대해서 이진 탐색이 가능할지에 대해서 생각해보자. 정확히는, 이를 만족하는 decision tree를 만들 수 있을 지에 대해서 생각해보자. 약간 직관에 의존하는 풀이임을 유념해줬으면 한다 ㅠㅠ (아래 정해에 자세한 증명이 나와있다)

ai가 작은 순으로 주어지기 때문에, greedy한 전략으로 decision tree를 만들 수 있다. 수 X를 작은 순서대로 집어넣으면서, 가장 왼쪽에 있는, 깊이 X인 노드에 i를 배정하자. 이러한 greedy 전략으로 decision tree를 만들 수 있음은, Sigma(2 ^ (-ai)) <= 1임을 의미한다. 이에 대해서는 깊이 inf에 있는 2^inf개의 노드 중 얼마의 비율이 각각의 수에 의해서 덮이는지를 생각해보자.

이 관찰을 하면 처음으로 물어볼 수 있는 정수에 대해서도 판단할 수 있는데, 정수 k를 처음으로 물어볼 수 있으려면, [1, k] 구간에 있는 수를 decision tree의 루트의 왼쪽 자식에, [k+1, N] 구간에 있는 수를 decision tree의 루트에 오른쪽 자식에 몰아넣을 수 있으면 된다. 입력으로 주어진 수를 1씩 빼면 결국 원래 문제로 환원된다.

이제, 문제는 Sigma(2 ^ (-ai)) <= 1인지를 판단하는 것이다. 이는 stack을 사용해서, 작은 순서대로 넣는데, 만약에 stack의 top이랑 현재 넣고자 하는 원소가 같다면, top을 지우고 현재 넣고자 하는 원소를 1씩 빼고.. 이걸 반복하면 증가 수열에 대해서 O(N)에 할 수 있다. [1, k] 구간에서 이를 만족하는 가장 큰 k / [k+1, N] 구간에서 이를 만족하는 가장 작은 k는 parametric search를 통해 O(lgN)에 구할 수 있다. (이 부분을 구현하는 방법이 다양한데, 당시 cubelover는 O(N)에 전부 할 수 있다고 했다. 나는 그냥 parametric search로 검수했다.. 대회 당시에는 std::set을 사용하는 풀이가 제일 인기있었다.)

정해 슬라이드