대회실습 5 (6.4)

<POI>

역대 POI 문제 중 ploughing, subway, railway 문제를 한 셋으로 풀었다.

처음 문제 세 개를 훑어 본 후 ploughing과 subway는 일단 제쳐 둔 뒤 railway 문제에 대해 뭔가 쉬운 그리디가 떠올랐고, 1시간 좀 안 되게 열심히 노력한 결과 그게 틀렸다는 것을 알 수 있었다... 습관이 참 무섭다.

그냥 18점 naive 풀이를 긁은 후 ploughing으로 넘어와서 다시 생각을 해 봤는데 O((HW)^2) 말고는 아직 잘 모르겠었다. subway도 마찬가지로 "리프 쌍들을 적절히 잘 고르면 된다"라는 것에서 더 넘어가지를 못 했다.

railway 문제에 대해 다시 고민해 본 결과 풀이에 접근할 수 있었다. 기차가 들어오는 순서가 정해지면 각 기차가 몇 번째 기차까지 들어온 이후 스택을 빠져나가는지가 바로 정해지고, 결국 각 기차는 "자기가 빠지기 전에 들어오는 자기보다 큰 기차"를 모두 자기가 들어간 반대편에 보내야 한다는 조건이 된다. 이를 바탕으로 기차들의 관계에 해당하는 그래프를 O(N^2) 시간에 만들어 이분 그래프인지 판별하면 된다. 이분 그래프라면 색을 적절히 정해서 답으로 출력하면 된다. 이 풀이를 짜면 47점을 받을 수 있다. 이후 이 과정을 적절히 최적화하는 방법을 고민해 보았는데 잘 떠오르지 않았다. (사실 예전에 JOI Spring camp 2017에서 이와 매우 비슷한 문제를 본 적이 있던 것 같다. 그 때도 여기까지밖에 생각 못 했던 것 같다)

ploughing을 다시 고민해 보니 이번에는 제대로 생각을 할 수 있었다. 결국 모든 밭을 갈기 위해서는 세로선을 모두 깎거나, 가로선을 모두 깎아야 한다. 가로선을 모두 깎기로 정했다면 (세로선의 경우는 그냥 판을 x-y 대칭시키면 된다) 임의의 두 세로선 사이 구간 [s, e]에 대해 가로선을 위/아래 각각에서 최대한으로 깎아 내면 어디까지 줄일 수 있는지가 정해지므로 이를 먼저 구한 뒤 (O(HW)에 구해진다) 처음 상태인 구간 [1, W]에서 가로선을 모두 깎을 수 있는 어떤 구간 [x, y]까지 세로선을 몇 번 깎아서 갈 수 있는지를 BFS로 구해주면 된다. 다행히도 코딩이 어렵지 않아서 금방 맞출 수 있었다.

나머지 시간 동안 subway도 생각해 보고 railway도 생각해 보았는데 둘 다 더 이상 아무것도 떠오르지 않았다...

5시간 대회를 한다 치면 (특히 요즘들어) 처음 1시간 정도에 아무것도 못 하는 때가 많은 것 같다. 처음에 잠깐 생각해 본 뒤 모르겠다고 갈팡질팡하다가 조금 시간이 지난 후 다시 차분히 생각을 정리하다가 풀이를 생각해내는 경우가 많은데, 처음부터 차분히 생각해야 될 것 같다. 시간을 좀 더 효율적으로 썼다면 subway를 긁을 수는 있었을 것 같은데 아쉽다.