대회실습 2 (5.12)

<APIO 2013>

문제를 다 읽은 후 잠시 생각을 해 본 결과 1, 2번은 일단 전혀 모르겠었다. 생각나는 대로 적당히 긁은 뒤 그나마 하면 점수가 나올 것 같았던 3번을 잡았다.

3. Tasks Author (데이터 만들기)

Single source shortest path 문제와 vertex coloring 문제를 푸는 코드에 대해 어느 것은 시간초과를 내고(cnt 변수를 100만 이상으로 증가시키고) 어느 것은 통과시키는 데이터를 만드는 문제다. 총 8가지의 subtask가 다음과 같이 나뉘어 있다.

(SSSP : 최단경로 / Mystery : vertex coloring)

subtask 1, 3 :  n = 101이고 간선 없는 데이터 넣으면 된다. 손으로도 20초면 만든다.

subtask 2:  BellmanFord 코드와 Floyd 코드를 살펴보면 연산 수가 각각 NMQ와 N^3이다. Q는 최대 10이고, N=100일 때 M=1050 정도가 되게 할 수 있어 그런 데이터를 만들어 넣으면 된다. BellmanFord에서 매 iteration마다 갱신이 일어날 수 있도록 간선을 N-1개 쓰는 경로를 적절히 넣어주어야 함에 유의.

subtask 5: N=300, Q=10일 때 M=347이 최대이다. Dijkstra는 알아서 잘 돌아가니(?) 그냥 그렇게 만들어 넣으면 된다.

subtask 4, 6: 가장 어려운 subtask인 것 같다. Dijkstra 알고리즘은 음수 간선이 있을 때 제대로 동작하지 않으니, 음수 간선을 적절히 넣어서 Dijkstra가 엄청 많이 돌게 만들면 된다. 나는 대회 중에 다음과 같은 구조를 만들었다.

이렇게 하면 각 삼각형 부분에서 똑같은 일을 2번씩 하도록 만들 수 있고, 총 연산 횟수가 2^(n/2) 정도에 비례하게 만들 수 있다.

끝나고 지금 다시 보니 -999999, -499999, ...., 이렇게 안 하고 그냥 -1로 다 채워도 될 것 같은데 왜 저렇게 했는지는 모르겠다. 맞았으면 됐지(?)

subtask 7: 문제 조건에 따르면 정점 71개, 간선 1501개로 된 그래프를 만들어야 하는데, 아무렇게나 간선을 그으면 시간 초과가 난다..

subtask 8: 25점이나 되는데 생각보다 쉽다. 정점이 많을수록 좋을 것 같으니 최대 수인 999개로 채우고, 간선을 최소 수인 1501개를 쓰기로 하면 마지막 몇 개를 제외하고는 4개씩 완전그래프로 묶어주면 백트래킹 알고리즘이 각 컴포넌트별로 독립적으로 작업을 하니 시간 초과가 나지 않는다.

오히려 점수가 많이 걸린 subtask를 풀 때보다 점수가 적게 걸린 쉬운 subtask를 풀 때 삽질을 많이 한 것 같다. 계산을 좀 더 침착하게 한 뒤 코딩에 돌입할 필요가 있다.

2.  Toll

가중치 그래프에 간선 몇 개를 원하는 가중치로 추가한 후 MST를 만든 뒤, 1번 노드가 루트일 때 MST에 포함된 모든 새로 추가된 간선에 대해 (그 간선을 기준으로 나뉘는 아래쪽 서브트리의 노드의 값의 합 * 간선의 가중치)의 합을 최대화하는 문제다.

처음에 이상한 생각을 했다가 잘못된 풀이를 짜고 (K=1일 때는 맞는 풀이여서 다행이었다) 시간을 약간 날렸다. 3번을 풀고 와서 다시 생각해 본 결과, 각 새로운 간선은 원래 MST에서 새로운 간선이 잇는 두 점 사이의 경로상에 놓인 간선 중 가장 비싼(가중치가 큰) 간선을 끊고 그것을 대체할 수 있고, 그 때 그 간선에 해당하는 아래쪽 서브트리의 노드의 값의 합은 그 끊긴 비싼 간선에 해당하는 아래쪽 서브트리와 같다는 것을 알 수 있었다.

그런데 새로운 간선들이 만드는 경로가 겹칠 때 어떻게 처리할지가 헷갈렸고, 이에 대해 시간을 써서 고민을 해 보았지만 결국 답에 다다르지는 못했다.

1. Robots

n x m 격자에 벽, 회전판(위를 통과하면 시계/반시계 방향으로 90도 회전)이 있고 1~9까지 번호가 붙은 로봇들을 네 방향으로 밀 수 있다. 인접한 번호를 가진 로봇들은 합쳐져 숫자 구간을 나타내는 로봇이 되고, 결국 전체 로봇을 하나의 구간으로 합치는 것이 목적일 때, 로봇을 미는 최소 횟수를 구해야 한다.

문제를 처음 봤을 때부터 끝까지 아무 생각이 들지 않았다. 30점 풀이는 n=2일 때라서 그냥 두 로봇이 어느 한 칸에 도달하는 데 필요한 횟수의 합을 최소화하면 되기 때문에 그것을 얼른 긁고 (그나마도 문제를 대충 읽어서 시간을 좀 날렸다) 다른 문제로 넘어간 뒤 다시 돌아오지 못했다. 중간에 생각을 잠깐씩 해 봤는데 그때도 계속 아무것도 모르겠었다.

종합 후기

3번을 잡은 것은 결과적으로 올바른 판단인 것으로 밝혀졌다. 나머지 두 개에 대해 아무것도 모르겠었기 때문이다. (지금도 잘 모르겠다) 약간 졸린 상태로 해서 그런지 생각 속도가 느려진 것 같았다. 천천히 풀이를 생각해 보면 생각이 날지도 모르겠는데 아직은 아무 아이디어도 없다. 이런 게 IOI에 나오면 어떡하나 하는 생각도 든다. 3번 문제는 재미있었던 것 같은데 나머지는 너무 어려워서 그런지 별로 마음에 와 닿지 않았다.

특히 1번 같은 격자에서 최단 경로 비슷한 걸 찾는 문제에 내가 많이 약한 것 같다. 현수는 저런거 잘 풀던데... 국대교육가서 많이 배워야겠다.