레이팅 미적용농부 존의 소 연합(United Cows of Farmer John, UCFJ)이 연례 후프볼 챔피언십에 출전했다! UCFJ의 \(N\) \((1 \le N \le 7500)\)마리 소로 이루어진 팀은 후프볼에서 농부 뇌즈의 팀을 간발의 차로 꺾고 금메달을 차지했다.
소들은 이미 시상식을 위해 한 줄로 늘어서 있다. 소들은 농부 존이 줄의 연속 부분 수열마다 하나씩, 총 \(\frac{N(N+1)}{2}\)장의 단체 사진을 찍어 주기를 원한다.
그러나 팀의 감독인 농부 존은 소들이 줄을 서는 방식에 매우 까다롭다. 구체적으로, 그는 부분 수열이 팰린드롬을 이루지 않으면 그 부분 수열의 사진을 찍기를 거부한다. 팰린드롬이란, 부분 수열의 길이 이하의 모든 양의 정수 \(i\)에 대해, 부분 수열의 왼쪽 끝에서 \(i\)번째 소의 품종이 오른쪽 끝에서 \(i\)번째 소의 품종과 같아야 한다는 뜻이다. 각 소의 품종은 건지(Guernsey) 또는 홀스타인(Holstein)이다.
줄의 \(\frac{N(N+1)}{2}\)개의 연속 부분 수열 각각에 대해, 그 부분 수열을 팰린드롬으로 재배열하는 데 필요한 최소 교환 횟수를 구하여라 (불가능하면 \(-1\)). 한 번의 교환은 부분 수열에서 인접한 두 소를 골라 서로 자리를 바꾸는 것이다. 이 값들의 합을 출력한다.
필요한 교환 횟수는 각 연속 부분 수열마다 독립적으로 계산됨에 유의한다 (소들은 사진 사이마다 원래 위치로 돌아간다).
Problem credits: Mythreya Dharani and Benjamin Qi
채점 방식
예제를 제외하고 열다섯 개의 테스트 케이스가 있으며, 각각
\(N \in [100, 200, 500, 1000, 2000, 5000, 5000, 5000, 5000, 5000, 7500, 7500, 7500, 7500, 7500]\)
에 해당한다.
Problem credits: Mythreya Dharani and Benjamin Qi
길이 \(N\)의 G와 H로 이루어진 문자열로 표현된 줄이 주어진다.
줄의 모든 \(\frac{N(N+1)}{2}\)개의 연속 부분 수열에 대한 앞서 말한 값의 합을 출력한다.
GHHGGHHGH12The first four contiguous subsequences are G, GH, GHH, and GHHG. Both G and GHHG
are already palindromes, so they contribute \(0\) to the sum. GHH can be
rearranged into a palindrome using a single transposition, so it contributes \(1\)
to the sum. GH cannot be rearranged into a palindrome using any number of
transpositions, so it contributes \(-1\) to the sum.
Another contiguous subsequence that contributes to the sum is HHGG. This can be
rearranged into a palindrome using two transpositions.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Platinum