Atcoder Wide-Flip 문제인데요.
https://atcoder.jp/contests/arc088/tasks/arc088_B
제한조건에서
|S|<= 10만
이니까 O(N) 이나 O(NlgN)으로 풀어야 할거 같아서
곰곰히 생각해보았는데요.
처음에 생각한건 주어진 문자열을
string str이라고 하면
int left = str[0]; 이라 하고
int right= str.size()-1; 이라고 했어요.
[l,r]
[l,r-1] , [l+1, r]
[l,r-2], [l+1,r-1] , [l+2, r]
.....
이런식으로 만들어서 조합을 해볼까 하다가 N의 길이를 생각해보니 안될 것 같더라구요.
그래서
유심히 보다보니
그러면 str 에서 연속된 0이나 1의 가장 긴 길이를 찾아서 구해보면 되지 않을까 생각했어요.
ex ) 100111011110
일때, 1 이나 0으로 가장 연속적으로 긴 부분은 right= 11, left=8이니까
답은 right-left+1의 길이에서 +1을 더 더한 값(결과적으로 right-left+2) 이라고 생각을 했죠. 이곳에서 예외처리로 가장 긴 문자열의 길이가 포함되는
left나 right가 str[0]이나 str[str.size()-1]인 곳에서는 답을 right-left+1이라고 했습니다.
그런데 case 16.txt 번 부터 Wrong Anser가 뜨네요.
제 방법에 예외가 있을까요?
나도 알린이긴 한데, (1) K가 정해졌을 때 그리디로 O(|S|)에 가능 유무를 확인할 수 있고, (2) 최대 K에 대해 binary search 하는 것이 가능하다면 O(|S|log |S|)에 구할 수 있겠네.
근데 되나?
다른 풀이 시도: S -> S' 으로 변환하는 함수를 하나 정의 한다. S[i] != S[i+1]일 경우 S'[i] = 1, 아닐 경우 0
저렇게 풀수도있구나 신기하네
S에서 구간을 뒤집는 operation은 S'에서 1을 한 개나 두 개 삭제하는 operation이다.
S'에서 1 두 개 삭제 경우: S에서의 (r-l+1) = S'에서 삭제하는 두 1 사이의 길이
S'에서 1 한 개 삭제 경우: S에서의 (r-l+1) = S'에서 삭제하는 1과 양 끝 단 사이의 길이 중 큰 값
S'에서 1을 모두 한 개 씩 삭제하는 경우에 S에서의 (r-l+1)의 최대값, 즉 K가 가장 크다.
즉 S'에서 각 1에 대해 해당 1과 양 끝 단 사이의 길이 중 큰 값을 계산하고, 계산값 중 최소값을 K로 취하면 된다.
풀리네:
https://atcoder.jp/contests/arc088/submissions/3863756
음.. 감사합니다. 아까 보고선 계속 어떤 원래로 되고 있나 생각하고 있는데, 쉽지 않네요. 알거 같으면서
https://atcoder.jp/contests/arc088/submissions/3866483
내가말한 풀이는 이거임 간-단
오 감사합니다. 코드보고 추적해보겠습니다.!!
으앙 ㅠ 이해가 되버렸네요.
모두 답변 감사합니다 :)