희 호 씨, 58 주차.

제목 분석
주어진 문자열 S, S 에 하위 문자열 S' 만족 'aa... abb... bcc... c 가 있 는 지 확인 합 니 다.그 중에서 abc 는 연속 적 인 세 글자 이 고 a, b, c 의 수량 이 같다.
원래 제목 에 수량 이 같은 연속 n (n > 3) 자 모 를 사용 하 는 것 도 가능 하 며, 실제 n > 3 이 되 었 을 때 n = 3 의 상황 이 반드시 포함 되 어 있다.예 를 들 어 'abcd' 는 'abc' 와 'bcd' 두 개의 합 법 적 인 하위 문자열 을 포함한다.
알고리즘 분석
가장 기본 적 인 사 고 는 S 의 모든 문자열 에 대해 요 구 를 만족 시 키 는 지 여 부 를 판단 하 는 것 이다.하위 문자열 의 출발점, 종점, 그리고 합 법 적 인지 확인 합 니 다.
S 의 길이 가 N 이 라 고 가정 하면 시간 복잡 도 는 O (N ^ 3) 입 니 다.

For i = 0..N-1
    For j = 0..N-1
        check(S[i..j])
    End For
End For

이런 방법 은 N 의 조금 큰 데이터 에 있어 서 시한 을 초과 할 것 이다.
더 나 아가 합 법 적 인 하위 문자열 에서 똑 같은 자모 가 항상 연속 되 기 때문에 우 리 는 (c, n) 으로 똑 같은 자 모 를 나타 내 는 것 도 좋 습 니 다. 예 를 들 어 'aa' 는 (a, 3), 'bb' 는 (b, 2) 로 표시 합 니 다.
우 리 는 전체 문자열 S 를 (c, n) 로 표시 하여 {(c [1], n [1], (c [2], n [2]),... (c [t], n [t])} 의 서열 을 얻 었 다.그 중에서 우리 의 합 법 적 인 하위 문자열 도 {(a, n), (b, n), (c, n)} 로 표시 할 수 있 습 니 다.
이 알고리즘 은 시퀀스 {(c [1], n [1]), (c [2], n [2],.
예 처리 시간 은 O (N) 이 고 얻 은 서열 의 길이 가 최대 N 이기 때문에 전체적인 시간 복잡 도 는 O (N) 로 낮 아진 다.

For i = 1 .. t-2
    If (c[i]+1 == c[i+1] and c[i+1]+1 == c[i+2]) and (n[i] == n[i+1] == n[i+2])
        Return True
    End If
End For

그러나 실제 운행 에서 이 알고리즘 이 정확 하지 않다 는 것 을 발견 할 수 있다.예 를 들 어 "aaaabbccc" 의 대응 하 는 서열 은 {(a, 4), (b, 2), (c, 3)} 입 니 다. 우리 위의 알고리즘 에 따라 합 법 적 인 하위 문자열 을 찾 을 수 없습니다.그러나 실제 적 으로 합 법 적 인 하위 문자열 'aabbcc' 가 존재 합 니 다.
분명히 문 제 는 우리 가 n [i], n [i + 1], n [i + 2] 에 대한 판정 에 있다.위의 반 례 를 통 해 알 수 있 듯 이 하위 문자열 에서 n [i], n [i + 2] 의 값 은 사실 변동 할 수 있 고 유일한 고정 값 은 n [i + 1] 의 값 이다.n [i] > n [i + 1] 일 때 우 리 는 앞의 몇 개의 자모 만 삭제 하면 n [i] = n [i + 1] 을 만 들 수 있다.같은 이치 로 n [i + 2] > n [i + 1] 에 대해 우 리 는 뒤의 자 모 를 삭제 합 니 다.따라서 n [i] > = n [i + 1], n [i + 2] > = n [i + 1] 만 있 으 면 반드시 변환 을 통 해 n [i] = n [i + 1] = = n [i + 2] 를 만 들 수 있다.
수정 후 우리 의 알고리즘 코드 는:

For i = 1 .. t-2
    If (c[i]+1 == c[i+1] and c[i+1]+1 == c[i+2]) and (n[i] >= n[i+1] and n[i+1] <= n[i+2])
        Return True
    End If
End For

결과 분석
실제 경기 에서 이 제목 의 통과 율 은 26% 에 불과 하 다.
그러나 경기 후 통계 에 따 르 면 대부분의 선수 들 은 소박 한 알고리즘 을 사용 해 규모 가 작은 데이터 포 인 트 를 통과 했다.이 문제 에서 10 ~ 60 점 의 점 수 를 얻 었 다.
재 미 있 는 것 은 한 선수 가 3 글자 연속 여 부 를 판정 하 는 데 그 쳤 고 60 점 을 받 았 다 는 점 이다.
한편, 70 ~ 90 점수 구간 에 분포 되 어 있 는 프로그램 은 무 작위 로 몇 개의 견본 을 추출 한 결과 대부분이 정확 한 알고리즘 을 생각 한 것 을 발견 했다.이들 이 점 수 를 잃 게 된 주요 원인 은 여러 그룹의 데이터 초기 화 문제 다.

#include <cstdio>

int main() {
    int T;
    scanf("%d%*c", &T);
    while (T--) {
        int len;
        scanf("%d%*c", &len);
        char pre = getchar(), cur;
        int cnt = 1, num[3] = {0};
        bool flag = false;

        for (int i = 1; i <= len; i++) {
            cur = getchar();
            if (cur == pre) {
                cnt++;
            } else {
                num[0] = num[1];
                num[1] = num[2];
                num[2] = cnt;
                cnt = 1;

                if (num[0] >= num[1] && num[1] <= num[2] && num[1])
                    flag = true;

                if (cur - pre != 1)
                    num[0] = num[1] = num[2]= 0;
            } 

            pre = cur;
        }
        flag ? puts("YES") : puts("NO");
    }
    return 0;
}