레이팅 미적용농부 존은 최근 새로운 소 \(N\)마리 \((3 \le N \le 5 \times 10^5)\)를 들여왔는데, 각 소의 품종은 건지(Guernsey) 또는 홀스타인(Holstein)이다.
소들은 현재 일렬로 서 있고, 농부 존은 연속한 세 마리 이상의 소로 이루어진 모든 구간의 사진을 찍으려 한다. 하지만 그는 건지 품종의 소가 정확히 한 마리이거나 홀스타인 품종의 소가 정확히 한 마리인 사진은 원하지 않는다. 그 한 마리뿐인 소가 고립감과 소외감을 느낄 것이라고 생각하기 때문이다. 세 마리 이상의 소로 이루어진 모든 구간의 사진을 찍은 뒤, 그는 건지가 정확히 한 마리이거나 홀스타인이 정확히 한 마리인, 이른바 "외로운" 사진을 모두 버린다.
소들의 배치가 주어질 때, 농부 존이 버리게 될 외로운 사진이 몇 장인지 구하는 것을 도와주자. 두 사진은 줄에서 시작하는 소 또는 끝나는 소가 다르면 서로 다른 사진이다.
출제자: Nick Wu
채점 방식
- 테스트 케이스 2-4는 \(N \le 50\)을 만족한다.
- 테스트 케이스 5-10은 \(N \le 5000\)을 만족한다.
- 조금 더 도전적인 테스트 케이스 11은 추가 제약이 없다. 이 케이스의 답은 표준 32비트 정수에 담기에 너무 클 수 있으므로 더 큰 정수 자료형(예: C++의 64비트 "long long int")이 필요할 수 있음에 유의한다.
출제자: Nick Wu
입력의 첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 문자로 이루어진 문자열이 주어진다. \(i\)번째 문자가 G이면 줄에서 \(i\)번째 소는 건지이다. 그렇지 않으면 H이며 \(i\)번째 소는 홀스타인이다.
농부 존이 외롭다는 이유로 버리게 될 사진의 수를 출력한다.
5
GHGHG3Every substring of length 3 in this example contains exactly one cow whose
breed is Guernsey or exactly one cow whose breed is Holstein --- so these
substrings represent lonely photos and would be thrown out by Farmer John.
All longer substrings (GHGH, HGHG, and GHGHG) are
acceptable to him.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Bronze