IOI 멘토교육 20190531

문제셋: JOI Spring Training Camp/Qualifying Trial 2015/2016 Day 2

​

Employment

이런 유형의 문제를 예전에 고민해본 경험이 있어서 덕분에 거의 보자마자 풀이가 떠올랐다.

평가치가 높은 사원부터 고용한다고 생각해보면, i번째 사원이 고용될 때 i-1번째 사원과 i+1번째 사원이 이미 고용되어있었는지 아닌지 여부에 따라 그룹의 개수가 어떻게 변화하는지 알 수 있다. i번째 사원마다 그룹의 개수가 어떻게 변화하는지의 값을 C[i]라고 하자. 이제 펜윅 트리와 같은 구간합 자료구조를 통해서 평가치가 가장 높은 사원부터 고용되는 사원들 중 평가치가 가장 낮은 사원까지의 C[i]값을 더하면 그룹의 개수를 알 수 있다. i번째 사원의 평가치가 업데이트될 때 바뀔 수 있는 것은 C[i-1], C[i], C[i+1]뿐이므로 이 세 개의 값을 펜윅트리에 업데이트해주면 된다. 처음엔 영향받는 값이 C[i]뿐이라고 생각했었는데, 이 실수 때문에 코딩 시간이 조금 길어졌다. 풀이가 생각났다고 바로 코딩하지 말고 좀 더 생각한 다음에 코딩하는 습관이 필요한 것 같다. 또 평가치가 같은 사원끼리의 처리가 살짝 헷갈렸는데, 평가치가 같으면 번호가 낮은 사원부터 고용한다고 정해버리니 생각하기가 쉬워졌다.

1시간 정도 투자해서 100점을 받을 수 있었다.

​

Sandwich

처음엔 문제를 봤을 땐 그냥 귀찮은 최단경로 문제인 줄 알았는데, 전혀 아니었다. 이상한 DP 풀이가 생각나서 바로 코딩해서 제출해봤지만 조금만 생각해봐도 반례가 나오는 풀이였다. 진짜 조금만 생각해봐도 틀리다는 걸 알 수 있는 풀이였는데, 코딩에 들어가는 타이밍이 너무 빨랐다. 그러고 나서 계속 고민해봤는데, 중복되서 카운팅되는 샌드위치들을 어떻게 처리할지 감이 오질 않았다. 주변에 있는 3개의 샌드위치 모양에 따라 케이스를 나눠서 처리하려고도 해 봤지만 잘 되지 않았다. 또 기준 샌드위치에서 시계방향으로 쭉 가보고, 반시계방향으로 쭉 가서 샌드위치들을 돌려깎는다는 느낌으로 세 보려고 했는데, 필요한 샌드위치들의 모양이 너무 다양해서 효율적으로 세는 것은 불가능해보였다. 3번을 먼저 풀고 오니 10분밖에 남지 않아서 결국 이 문제는 0점으로 마무리되었다... 처음에 생각했던 이상한 DP 풀이를 조금만 고치면 부분점수를 받을 수 있었을텐데 섭태를 긁지 못한 것이 아쉽다.

​

Toilets

처음에 문제를 봤을 땐 괄호 문자열의 느낌이 났다. 그런데 괄호 문자열이랑 비슷하기도 하면서 오묘하게 달랐다. 관찰을 조금만 더 해 보니 뒤에 여자가 없는 상태에서 남자와 남자가 연속으로 있으면 실패하는 것이므로 뒤에서부터 여자면 +1, 남자면 -1을 해서 누적합이 -1 미만이 되면 실패라는 사실을 알아냈다. 그러면 -(누적합의 최솟값)-1이 답 아닌가? 하는 생각으로 이걸 짜서 내 봤지만 0점이 나왔다. 지금 생각해보니 36점을 받았어야 했는데 -(누적합의 최솟값)-1이 음수인 경우를 처리 안해서 0점이 나왔던 것 같다. 이것 때문에 이 풀이가 틀린 줄 알았고, 100점으로 가는 길을 많이 돌아간 것 같다.

​

일단 감이 잘 안 오고 대회 시간도 얼마 남지 않아서 부분점수를 받기로 했다. 여자를 k칸 뒤로 밀었을 때 성공하는가? 여부로 k를 이분탐색하는 풀이로 서브태스크 1, 2를 긁었다. 이때 k칸 미는 걸 어떻게 효율적으로 할지 고민됐는데, 마지막에 있는 k명의 남자를 맨 앞으로 보내면 간단히 해결되는 문제였다. 여기까지 하고 나서 생각해보니 이분탐색이랑 아까 시도했던 누적합 아이디어를 합치면 만점이 나올 것 같았다. (사실 이분탐색은 필요 없었다... ㅠㅠ) 문제는 서브태스크 3의 N제한이 $ 10^{18} $이라는 점이다. 좀 더 생각해보니 문자열이 반복되면 반복되는 첫번째 문자열 또는 마지막 문자열에서 누적합의 최솟값이 나타난다는 걸 알 수 있었고, 이를 코딩하여 만점을 받았다.

​

처음에 시도했던 풀이를 좀 더 엄밀히 증명하거나 디버깅을 좀 더 시도했다면 100점을 좀 더 일찍 받을 수 있었을텐데, 직관적으로 이렇게 하면 되지 않을까? 아님 말고.. 식으로 시도했던 게 문제가 됐던 것 같다.

​

​

​

전체적으로 풀이를 생각한 뒤 코딩을 시작하는 타이밍이 조금 빠른 것 같다. 코드포스 같이 시간이 중요한 대회에서는 모르겠지만, 이런 OI류 대회에서는 코딩을 조금 더 늦게 시작하는 습관을 들여야 할 것 같다. 또 이건 매번 느끼는 점이지만 서브태스크를 먼저 긁고 만점을 받는 것이 훨씬 안정적이고 생각보다 빠른 방법인 것 같다.