Reenact

이것도 전형적인 이분탐색 문제인데 아무리 생각해도 시간 복잡도가 O(N^2 logN)으로 시간이 10^8을 넘어 시간 초과가 뜨지 않을까 제출 전에 계속 고민했었다. 근데 아무리 고민해도 시간 복잡도를 더 줄일 수가 없을 것 같아 혹시나 해서 이대로 제출했더니 통과해버렸다.. 풀이를 검색해보니 다른 사람들도 시간 복잡도가 나와 같았는데 1억을 넘어도 시간 초과를 안하고 통과할 수도 있다는 걸 처음 알았다. 지금까지는 1억 넘으면 무조건 시간 초과인줄 알았는데... 시간 복잡도가 애매하고 더 줄이기 힘들어보이면 일단 제출하고 봐야되나보다.. 암튼 새로운 사실을 알아서 기쁘다! 아 그리고 여기서 정답이 되는 cnt값을 int가 아닌 long long으로 지정해주었는데, 이유는 최대 10000C3이 될 수 있..

전형적인 이분 탐색 문제였다. 여기서 STL의 upper_bound와 lower_bound 함수를 이용해 조금 더 간단하게 풀 수 있는데 나는 그냥 이분탐색을 직접 구현하였다.

처음 생각했을 땐 이분탐색 압축으로 풀면 되겠다 싶었는데 계속 시간 복잡도가 1억을 넘기는 상황이 발생하였다. 그래서 계속 고민을 계속 하다가 위와 같은 방식으로 풀면 10^6대로 풀 수 있었다. 아이디어는 대충 한 우주 안의 행성을 압축한다음 문자열로 저장하는 것이었다. 이 때 문자열끼리의 비교는 O(문자열 최대 길이)만큼 시간이 걸린다고 하니 그 부분도 고려해야 하였다.

가장 긴 부분수열의 시작점을 처음과 끝 각각 2가지에 대해 구한 다음에 합이 가장 긴 경우에서 1을 빼주면 된다!

아이디어는 조금 생각해보면 크게 어렵지 않다 전기줄의 도착점들을 시작점이 작은 순서에서 큰 순서대로 배열해준다. 거기서 가장 긴 증가하는 부분 수열을 구한 다음에 전체 전기줄 개수에서 빼주면 된다!

열심히 해야지 !

양수인 애들을 pos에, 0이하인 애들을 npos에 저장해놓는다. 그리고 양수인 애들은 가장 큰 애들 2개를 선택해서 곱하고 더하는 걸 반복하다가 1이 있으면 그냥 더한다 음수인 애들은 가장 작은 애들(절댓값이 가장 큰 애들) 2개를 선택해서 곱하고 더하는 걸 반복한다

시작점이 작은 것에서 큰 순서대로 배열하고 start와 end를 update해가면서 선분이 잘릴 때마다 그 길이를 더해주면 된다!