ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#7038

중복문자열 1s 1024MB

問題

중복문자열이란, 길이가 짝수이며 앞쪽 절반의 부분문자열이 뒤쪽 절반의 부분문자열과 같은 문자열을 일컫는다.

예를 들어, abcabc는 중복문자열이지만 ababab는 중복문자열이 아니다.

길이 2N의 문자열에서 인접한 위치의 문자를 교환하는 연산을 적절히 시행하여 전체 문자열이 중복문자열이 되도록 하고 싶다.

인접한 위치의 문자를 교환하는 연산의 최소 시행 횟수를 구하시오.


入力

첫 줄에 N이 주어진다. (1<=N<=100000)

그 다음 줄에 길이 2N의 영어 소문자로 구성된 문자열이 주어진다.

단, 이 문자열은 항상 중복문자열이 되도록 할 수 있다.


出力

중복문자열이 되게 하는 연산의 최소 횟수를 한 줄에 출력하시오.


部分問題

番号 点数 条件
#110点

문자열에 'a'가 N개, 'b'가 N개 주어진다.

#220点

각 문자는 최대 2번 등장한다.

#320点

앞쪽 절반의 문자의 집합과 뒤쪽 절반의 문자의 집합이 같다. (중복 고려)

#420点

N<=1000

#530点

제한 없음


例題 #1

3
koeeok
3

例題 #2

3
kekoeo
1

例題 #3

4
soolnlsn
4

soolnlsn -> solonlsn -> solnolsn -> oslnolsn -> olsnolsn



出典

COCI 2021/2022 Contest #3

ログインしないとコードを書けません。