BOJ 34211 Duplicated Binary Strings

문제 링크입니다.

문제 요약

Part I

주어진 이진 문자열의 서로 다른 repetition의 개수를 구하세요. repetition은 어떤 문자열 $s$가 두 번 반복된 형태를 의미합니다. $s$가 다르면 서로 다른 repetition입니다.

Part II

길이가 100인 이진 문자열 중 repetition의 개수가 3(최소)인 것과 84(최대)인 것을 각각 하나 찾으세요.

풀이

Part I

문자열의 길이가 100 이하로 작아 간단한 나이브를 짜도 되고, 저는 해싱을 통해 ${\cal O}(N^2)$에 구현했습니다.

Part II - Minimize

0 또는 1 중 하나를 절대 반복하지 않도록 해를 구성하는 것은 매우 어려울 것이라 추측해 볼 수 있습니다. 그러니 사용할 수 있는 repetition으로 $00$과 $11$을 고정하고, 나머지 하나를 채운다는 느낌으로 접근합시다. 추가적인 repetition을 만들지 않고 0과 1을 최대 3개씩 나열할 수 있겠네요. 적당히 번갈아 가면서 나열하는 백트래킹을 짜서 돌리니 제 로컬 기준 10초 정도면 해를 찾을 수 있었습니다.

Part II - Maximize

제 해 구성의 기본적인 아이디어는 0을 잔뜩 나열하고 적당히 1로 0들을 묶음으로 끊어주는 것입니다. 이게 대충 문자 하나마다 repetition 하나가 적당히 많이 매칭되면 84라는 값이 나올 수 있을 거라 생각해서, $00100100$ 같은 구조를 많이 만들려 했고, 그 과정에서 만들어지는 repetition끼리도 0의 개수를 다르게 맞춰줘야 하니 적당히 0 개수가 늘어나도록 조정하다 보니까 80 언저리까지 점수가 늘길래 디테일한 부분을 적당히 수정해서 AC를 받았습니다.

코드

Part II는 사실상 Output Only 문제라 Output을 그대로 게시하기엔 좀 그래서, 적당히 가렸습니다.

#include "bitstrings.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int count_duplicated(string s){
	unordered_set<ll> ret[123];
	ll hash[123][123] = {};
	for(int i = 0; i < s.size(); i++) for(int j = 1; i+j <= s.size() && j <= 50; j++) hash[i][j] = hash[i][j-1]<<1|(s[i+j-1]&1);
	for(int i = 0; i < s.size(); i++) for(int j = 1; i+j+j <= s.size(); j++) if(hash[i][j] == hash[i+j][j]) ret[j].insert(hash[i][j]);
	int ans = 0; for(int i = 1; i <= s.size(); i++) ans += ret[i].size();
	return ans;
}

string find_weakest(){
	return "dQw4w9WgXcQ001011100010110001110010never gonna give you up0111000101100011100101100010111dQw4w9WgXcQ";
}

string find_strongest(){
	return "dQw4w9WgXcQ00001000001000000100000never gonna let you down0000001000000001000000010000000dQw4w9WgXcQ";
}