IOI 멘토교육 20190607

돈 셋: AGC034

 

A. Kenken Race

C < D인 경우와 C > D인 경우로 나누어 풀 수 있다. 전자의 경우에는 A와 D 사이에 연속된 돌이 없는지만 확인해주면 된다. 후자의 경우에는 추가적으로 Snuke와 Fnuke가 순서를 바꿀 수 있는지를 체크해줘야 하는데, B와 D 사이에 연속된 3개의 칸이 모두 비어있을 경우 순서를 바꿀 수 있음을 관찰하면 된다.

 

B. ABC

ABC를 BCA로 바꾼다는 걸 약간 다르게 해석해 보면, 'A'와 'BC'가 자리를 바꾼다고 해석할 수 있다. 그러면 문제는 자리 바꾸기 횟수의 최댓값을 구하는 것으로 바뀐다. A의 개수를 누적해주면서 BC가 나올 때마다 그 값을 답에 누적시키고, A도 BC도 아닌 문자가 나오면 A의 개수를 0으로 초기화하는 작업을 반복하면 O(N)에 문제를 해결할 수 있다.

 

C. Tests

일단 $c_i$는 $l_i$ 아니면 $u_i$이어야 한다. 타카하시가 아오키보다 덜 풀었으면 $l_i$로 설정하고, 더 많이 풀었으면 $u_i$로 설정하는 것이 이득이기 때문이다. 이제 i번째 시험에 k시간을 투자하면 k > b라면 $l_i*b + u_i*(k-b)$만큼 이득이고, k <= b라면 $l_i*k$만큼 이득임을 알 수 있다. 나는 여기까지 관찰하고 답을 이분탐색하려고 했는데, 잘 되지 않았다. 대회 막바지에 불확실한 가정 하나를 한 다음 이분탐색 풀이를 내 봤지만, WA를 받았다.

 

D. 

 

E. Complete Compress

C의 이분탐색 풀이가 잘 생각이 나지 않아서 잠깐 E의 풀이를 고민해보고, 심지어 구현도 조금 해 보다가 포기했는데, 지금 생각해보니 시간도 느리고 정확한 답을 내지도 못하는 알고리즘이었던 것 같다.

 

F.

 

C가 잘 풀리지 않는다고 E를 볼 게 아니라, 생각을 정리하고 침착하게 고민하는 시간을 가지는 것이 더 나았을 것 같다.

특히 AGC 같이 난이도가 정해져 있는 셋에서 어려운 문제를 먼저 푸는 건 그 문제를 확실히 풀 수 있을 때에만 해야 할 것이다. 지금까지는 어떤 문제에서 말리면 다른 문제를 풀다가 다시 돌아와서 그 문제를 풀었다. 이런 방법 말고도 침착하게 생각을 정리하는 방법으로 말린 상태를 벗어나는 연습도 해야 할 것이다.