chatterboy   1년 전

안녕하세요.

알고스팟에 있는 문제입니다.

https://algospot.com/judge/problem/read/ZEROONE

입력 스트링 S에 대해서 N번의 구간 질의를 수행하는 문제입니다. 해결 방향은 구간 질

의에서 D&C를 사용했습니다. O(NlgS)라고 생각하고(다시 생각해보니 O(NS)인 것 같습니다..)

구현을 했는데 두 가지 문제점이 발생했습니다. 먼저, 구간 질의 구현에 STL을 사용하니 TLE를

받았습니다. 그리고 구현에 STL을 사용하지 않고 구현을 하고나니 WA을 받았습니다. AC 여부를

떠나서 D&C로 구현했을때 무엇 때문에 WA를 받았을까요? 알려주시면 감사하겠습니다. ㅠㅠ

appa   1년 전

우선, 어떤 구간의 최댓값, 최솟값을 반복적으로 구해서 O(NS log S)일 거라 생각합니다. S개를 다 훑어보는데 log S의 깊이만큼 들어가야하니까요.

8번째 줄에 char N을 int N으로 바꾸면 정상적으로 TLE가 나옵니다.

이 문제의 경우에는 0과 1 밖에 없기 때문에 누적합을 이용해, 누적합의 변화가 있다면 그 사이에는 '1'이 포함된 것이므로 최댓값이 1인 것을 알 수 있고

누적합의 변화가 구간의 길이와 같다면 최솟값 또한 1인 것을 알 수 있을 것입니다.

chatterboy   1년 전

아하 ! 답변 감사합니다 :D !!

댓글을 작성하려면 로그인해야 합니다.