국가대표 멘토링 교육 2주차 후기

일요일날 CEOI 2018 Day1을 돌았다!

 

A. Cloud Computing

 

음... ㅁㄴㅇㄹ 일단 나이브로 냅색해서 4억짜리 풀이는 생각했고, 4억 2초는 좀 그러니까(반복문도 두 번 돌아서 거의 8억) 더 빠른 풀이를 열심히 고민해보았다. 그래서 계속 고민해봤는데 몇 시간째 답이 안 나와서 그냥 나이브 냅색을 냈는데 660ms에 돌았고 그게 정풀이었다... 풀이는 간단하다. 가격순으로 정렬하고 dp[i][j]=i번째까지 봤고 j개를 이미 사놨을 때 얻을 수 있는 최대 이득 으로 dp식을 잡고 냅색하면 된다.

 

B. Global Warming

 

앞쪽에 -d를 더하는 것과 반대로 뒤쪽에 d를 더하는 것은 동치이다. 그리고 구간에 양수 d를 더할 거라면 그냥 그 뒷부분에도 쭉 더하는 게 이득이다. 음수 d를 더할 거면 그 앞부분에도 더해주는 게 이득이다. 그러니까 결국 특정위치부터 x를 쭉 더했을 때 최대 LIS 길이를 구하면 된다. 그냥 dp를 세울 수 있다. dp[i][0]=i에서 끝나고 아직 x를 안 더했을 때 LIS 길이, dp[i][1]=i에서 끝나고 이미 x를 더하는 과정을 거쳤을 때 LIS 길이. 세그먼트 트리로 LIS를 구하는 방법을 이용해주면 저 dp를 가볍게 풀 수 있고 끝난다.

 

C. Lottery

 

25점은 나이브로 풀린다. 그 초과는 모르겠다. 문제에서 뭔가 되게 무리한 요구를 하는 거 같고, KMP나 Suffix Array 같은 문자열 알고리즘을 사용할 거 같은 느낌도 드는데 그 부분에 대해서는 거의 모른다.