2020 SCPC 2차 예선 참가 후기

 어제 SCPC 2차 예선에 참가하게 되었습니다. 작년에도 참가를 하였는데 2차 예선에서 한문제 밖에 풀지 못해서 올해는 마지막으로 참가 할 수 있는 기회기도 하고 작년보단 더 늘었으면 하는 바람과 함께 참가를 하였습니다.

 

결과는 역시 무지하게 어렵습니다....... 너무어려워요 ㅠㅠ

 

물론 작년보단 많이 발전 한것 같습니다. 작년 데이터가 있길래 봤는데 1번만 맞췄었습니다 ㅋㅋ 올해는 그런데 참가자가 적은 것인지 문제 난이도가 어려웠던 건지 작년보다 문제를 맞춘 사람이 확실히 적네요.

문제에 대한 얘기를 해도 되는지 모르겠어서 자세히는 말하지 않겠습니다. 실제로 2번 문제인 고구마가 만점자가 더많은데 저도 1번문제 첨에 보고 모르겠어서 넘기고 고구마 부터 풀었습니다.

 

간략하게 말하자면 주어진 배열에서 구간에 대한 합이 최대가 되는 합을 구해야 하는데 이게 단순히 최대가 아니라 주어진 수 M 보다 작으면서 최대인 양을 구해야 하는 문제입니다. 따라서 저는 쭉 훑으면서 구간에 대한 합들을 set에 저장해놓고 lower_bound를 통해 구해 주었습니다.

 

그 다음에 3번 문제를 봤는데 엄청 어려웠습니다,, 길이 L짜리 구간들의 합에 대한 중간값을 찾아야 하는데 중간에 배열도 계속 바뀌고 이리저리 세그트리 쓰고 해봤는데 15점 밖에 못긁었습니다. 

 

4번,5번은 사실 읽지도 않았고 다시 1번으로 돌아가서 풀이가 갑자기 떠올라서 풀게 되었습니다. 저는 1번문제는 부분합을 이용해서 풀었습니다. 본선을 가려면 아무래도 3번까지는 다맞춰야 가능성이 있을 것 같습니다. 아쉽긴 하지만 그래도 나름 작년보다 잘푼것에 만족하며 글을 마치겠습니다.