제 2회 삼성 대학생 프로그래밍 경시대회 2차 예선 후기(SCPC 2016)

BOJ Camp 도중에 대회가 있어서 집중하지 못했다. Camp 문제들에 대한 참가자들의 질문에 답해주어야해서 힘들었다.

오전에 잠깐 해서 1,2,3번을 짜고 오후엔 저녁 먹고 난 이후에 4번 푼 게 전부였다.

1차와 달리 2차는 난이도가 많이 상승해서 다 풀지는 못했지만 만점자이신 dotorya님께 풀이를 다 설명들었다.

4, 5번은 문제 서술조차 요약하기 힘들기 때문에 그냥 후기 형식으로 글을 남김,

문제를 푼 순서는 2번 - 1번 - 3번 - 4번이다. 

2번은 정말 간단한 1차원 DP이기 때문에 별로 할 말이 없는데, 문제에 특이한 초기 조건을 읽지 못해서 3번이나 틀렸었다.

1번은 STL을 쓰면 계속 TLE가 나서 그 부분을 다 고치니까 간신히 만점이 나왔다.

3번은 직관적으로 가로선을 가장 아래에서부터 위로 올리면서 lazy propagation으로 풀었는데, 계속 TLE가 나서 원인을 찾지 못하고 포기했었다. 대회 이후에 만점을 받았던 분의 소스를 받아 자채적으로 데이터를 만들어 채점을 해보니 답도 다 맞고, 시간도 꽤나 빨리 나오는데 이해하기 힘든 부분이다. 내 소스가 최대 데이터 30개에서 2초 정도가 걸리는데 억울하다고 생각한다.

4번은 문제 이해에 30분 정도가 걸렸다. 문제를 다 이해하고 LCA가 1번 정점이 아닌 도로들에 대해서 도로의 양 끝 정점에서 다익스트라를 수행하고 LCA로 O(1)만에 여러 계산을 하면 92점을 받을 수 있다. 예제가 나와서 제출해보았는데 한 번에 92점이 나와서 다행스럽다. 4번 만점 풀이도 생각을 했지만, 전처리로 계산해야하는 것들이 너무 많았는데 당시 남은 시간은 40분 정도라 포기했다.

5번은 문제를 읽었을 때에 잘 이해가 되지 않아서 남은 시간에 4번을 푸는 게 더 효율적이라 생각해 풀지 않았다.

본선에서는 3번, 4번, 5번의 난이도 문제들 혹은 더 어려운 문제들이 주로 출제될 것으로 예상된다.