루미 알고리즘

#1102플래티넘XOR 최대XOR 최대

KOI 2024 2차코딩중등부 3번, 고등부 2번출제 나정휘이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

XOR 최대

원제: XOR 최대

문제

어떤 문자열에서 연속한 위치에 있는 1개 이상의 문자를 선택해 순서를 유지한 채로 나열해서 얻을 수 있는 문자열을 그 문자열의 부분문자열이라 한다. 예를 들어, 001001는 X=1001‾1X = 1\underline{001}1의 부분문자열이지만, Y=10101Y = 10101의 부분문자열은 아니다.

음이 아닌 두 정수 A,BA, B의 배타적 논리합 A⊕BA \oplus B는 다음과 같이 정의된다.

  • 이진법으로 생각했을 때, AA의 2k2^k의 자릿수와 BB의 2k2^k의 자릿수가 서로 다르면 A⊕BA \oplus B의 2k2^k의 자릿수가 11이고, 같으면 A⊕BA \oplus B의 2k2^k의 자릿수가 00이다. (단, k≥0k \ge 0)
  • 예를 들어 12⊕1012 \oplus 10은 12=1100(2),10=1010(2)12 = 1100_{(2)}, 10 = 1010_{(2)}이므로 1100(2)⊕1010(2)=0110(2)=61100_{(2)} \oplus 1010_{(2)} = 0110_{(2)} = 6이다.

00과 11로만 구성된 길이가 NN인 문자열 SS가 주어진다.

당신은 SS의 부분문자열 s1,s2s_1, s_2를 선택해서 만들 수 있는 g(s1,s2)g(s_1, s_2)의 최댓값을 계산해야 한다. g(s1,s2)g(s_1, s_2)는 다음과 같이 정의되는 함수이다:

  • SS의 부분문자열 ss에 대해, f(s)f(s)의 값은 ss를 이진법으로 해석했을 때의 값이다. 예를 들어, 만약 s=11010s = 11010이면 f(s)=26f(s) = 26이다.
  • g(s1,s2)g(s_1, s_2)는 f(s1)f(s_1)과 f(s2)f(s_2)의 배타적 논리합이다.

이때 s1s_1과 s2s_2가 서로 다를 필요는 없다. 즉, s1s_1과 s2s_2는 SS에서 일부가 겹쳐도 되고, 완전히 같은 문자열이어도 된다.

00과 11로만 구성된 문자열 SS가 주어지면, 가능한 g(s1,s2)g(s_1, s_2)의 최댓값을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤T≤1001 \le T \le 100
  • 2≤N≤1072 \le N \le 10^7
  • 모든 테스트 케이스에서 NN의 합 ≤107\le 10^7
  • SS는 00과 11로만 이루어진 길이가 NN인 문자열이다.

부분문제

  1. (17점) N≤30N \le 30, 모든 테스트 케이스에서 NN의 합 ≤300\le 300
  2. (20점) N≤200N \le 200, 모든 테스트 케이스에서 NN의 합 ≤2000\le 2000
  3. (13점) N≤3 000N \le 3\,000, 모든 테스트 케이스에서 NN의 합 ≤30 000\le 30\,000
  4. (12점) N≤2×105N \le 2 \times 10^5, 모든 테스트 케이스에서 NN의 합 ≤2×106\le 2 \times 10^6
  5. (38점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다.

각 테스트 케이스마다, 첫 번째 줄에 문자열의 길이 NN, 두 번째 줄에 00과 11로만 구성된 길이가 NN인 문자열 SS가 주어진다.

출력 형식

각 테스트 케이스마다 가능한 g(s1,s2)g(s_1, s_2)의 최댓값을 이진법으로 한 줄에 하나씩 출력한다. 단, 정답 앞에 필요 없는 00은 출력하지 않는다.

예제

예제 1

입력
4
3
010
5
10101
5
00100
5
11111
출력
11
11111
110
11110

첫 번째 테스트 케이스에서 s1=010s_1 = 010, s2=01s_2 = 01로 설정하면 g(s1,s2)=11(2)g(s_1, s_2) = 11_{(2)}을 만들 수 있다. 11(2)11_{(2)} 대신 011(2)011_{(2)}으로도 표현할 수 있지만, 정답 앞에 필요 없는 00을 출력하면 안 되므로 011011이 아닌 1111을 출력해야 한다.

네 번째 테스트 케이스에서 s1=11111s_1 = 11111, s2=1s_2 = 1로 설정하면 g(s1,s2)=11110(2)g(s_1, s_2) = 11110_{(2)}을 만들 수 있다.

예제 2

입력
4
2
00
2
01
2
10
2
11
출력
0
1
11
10

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.