고급반 6주차 풀이 - 으쌰으쌰 (10 / 13)

1. [14370] 전화번호 수수께끼 (Large) (Gold III)

숫자를 나타내는 영어단어들을 보면, 자주 나오지 않는 글자들이 있는 걸 볼 수 있습니다.

이를 사용해서 특정 숫자의 개수를 빠르게 판별할 수 있지 않을까요?

네, 됩니다. 심지어, 이 방식으로 10개의 숫자를 모두 정할 수 있습니다.

 

아래는 각 숫자의 개수를 찾기 위해 사용한 표이며, 이 순서대로 볼드체 처리한 글자를 사용해서 개수를 세주면 됩니다.

0

E

O

R

Z

2

O

T

W

4

F

O

R

U

6

I

S

X

8

E

G

H

I

T

3

EE

H

R

T

5

E

F

I

V

7

EE

N

S

V

1

E

N

O

9

E

I

NN

답이 없는 경우는 문제에서 제외해줬으니 위 방식대로 개수를 신나게 구해주면 됩니다.

int cnt[130], ans[12];

void f(int val, char ch, string s){
	ans[val] = cnt[ch];
	for (char c : s){ cnt[c] -= ans[val]; }
}

void Main(){
	int t; cin >> t;
	for (int tt = 1; tt <= t; tt++){
		cout << "Case #" << tt << ": ";
		string s; cin >> s;
		for (char ch : s){ cnt[ch] += 1; }
		f(0, 'Z', "ZERO");
		f(2, 'W', "TWO");
		f(4, 'U', "FOUR");
		f(6, 'X', "SIX");
		f(8, 'G', "EIGHT");
		f(3, 'H', "THREE");
		f(5, 'F', "FIVE");
		f(7, 'S', "SEVEN");
		f(1, 'O', "ONE");
		f(9, 'I', "NINE");
		for (int i = 0; i <= 9; i++){
			while (ans[i]--){ cout << i; }
		}
		cout << endl;
	}
}

2. [3356] 라디오 전송 (Platinum IV)

Z 배열을 구한 뒤, $i+z[i]=|S|$가 되는 가장 작은 $i$를 찾아주면 됩니다.

int z[1000020];

void Main(){
	int sl; string s; cin >> sl >> s;
	int st = 0, ed = 0;
	for (int i = 1; i < sl; i++){
		if (ed < i){
			int p = 0; while (i+p < sl){
				if (s[p] == s[i+p]){ p += 1; } else{ break; }
			} z[i] = p;
		}
		else{
			if (i + z[i-st] <= ed){ z[i] = z[i-st]; }
			else{
				int p = ed-i+1; while (i+p < sl){
					if (s[p] == s[i+p]){ p += 1; } else{ break; }
				} z[i] = p;
			}
		}
		if (i+z[i] - 1 > ed){ st = i; ed = i+z[i] - 1; }
	}
	for (int i = 1; i < sl; i++){
		if (i + z[i] == sl){ cout << i; return; }
	}
	cout << sl;
}

3. [1097] 마법의 문자열 (Platinum V)

어떤 문자열 $S$가 $S(i)$와 같아지게 하는 위치 $i$가 정확히 $K$개 있다는 건

문자열이 $|S|/K$를 최소 주기로 반복한다는 것입니다.

이는 "2. [3356] 라디오 전송" 문제처럼 Z배열을 써주면 풀 수 있으며, "최소" 주기인지만 추가적으로 판별해주면 됩니다.

 

$N,|S|$가 모두 작으니, $N!$가지의 모든 순열을 돌리면서 문자열을 합치고

Z 배열을 잘 사용해서 개수를 세주면 됩니다.

int n, k; string arr[10];
int sl, ptr;
int z[170];

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; sl += arr[i].size(); }
	cin >> k;
	if (sl%k != 0){ cout << 0; return; }
	ptr = sl/k;
	vector<int> v; for (int i = 1; i <= n; i++){ v.push_back(i); }
	int ans = 0;
	do{
		string s = "";
		for (int i : v){ s += arr[i]; }
		int st = 0, ed = 0;
		z[0] = sl; for (int i = 1; i < sl; i++){
			if (ed < i){
				int p = 0; while (i+p < sl){
					if (s[p] == s[i+p]){ p += 1; } else{ break; }
				} z[i] = p;
			}
			else{
				if (i + z[i-st] <= ed){ z[i] = z[i-st]; }
				else{
					int p = ed-i+1; while (i+p < sl){
						if (s[p] == s[i+p]){ p += 1; } else{ break; }
					} z[i] = p;
				}
			}
			if (i+z[i] - 1 > ed){ st = i; ed = i+z[i] - 1; }
		}
		bool res = 0;
		for (int i = 1; i <= ptr; i++){
			if (i + z[i] == sl && z[i] + z[ z[i] ] == sl){ res = (i == ptr); break; }
		}
		//cout << "TRY " << s << ' ' << res << endl;
		ans += res;
	}while (next_permutation(all(v)));
	cout << ans;
}

4. [5670] 휴대폰 자판 (Platinum IV)

트라이 + 시뮬레이션 문제입니다.

우선 입력받은 $N$개의 문자열들을 다 트라이로 저장한 뒤, 각 단어들을 누르는 걸 직접 시뮬레이션해주면 됩니다.

 

시뮬레이션은 아래와 같이 간단히 돌려줄 수 있습니다.

1. 우선 시작 정점에서 버튼을 눌러줍니다.
2. 다음 정점이 1종류밖에 없다면, 버튼을 누르지 않고 그 정점으로 이동합니다.
3. 그렇지 않다면, 버튼을 눌러서 다음 정점으로 이동합니다.
4. 현재 정점이 도착지가 될 때까지 2/3 번 과정을 반복합니다.

평균을 출력해야 하는데, 어차피 평균 = 합 / 개수니까 합을 구해주고 나중에 나눠주면 됩니다.

struct Nod{ int cnt=0; bool chk=0; int nxc=0; int nxt[30] = {}; };
vector<Nod> tri;

string arr[100020];

void psh(int ni, const string& s, int idx){ int sl = s.size();
	tri[ni].cnt += 1;
	if (idx == sl){ tri[ni].chk = 1; return; }
	int& nxt = tri[ni].nxt[ s[idx]-'a' ];
	if (nxt == 0){ tri[ni].nxc += 1;
		nxt = tri.size(); tri.push_back( Nod() );
	}
	return psh(tri[ni].nxt[ s[idx]-'a' ], s, idx+1);
}

ll ans = 0;
void qry(int ni, const string& s, int idx){ int sl = s.size();
	if (idx == sl){ return; }
	if (tri[ni].chk || tri[ni].nxc != 1 || ni == 0){ ans += 1; }
	return qry(tri[ni].nxt[ s[idx]-'a' ], s, idx+1);
}

void Main(){
	int n; while (cin >> n){
		tri.push_back( Nod() );
		for (int i = 1; i <= n; i++){ cin >> arr[i]; psh(0, arr[i], 0); }
		ans = 0; for (int i = 1; i <= n; i++){ qry(0, arr[i], 0); }
		cout << (ld)ans/n << endl;
		tri.clear();
	}
}

5. [13505] 두 수 XOR (Platinum III)

XOR은 이진수니, 각 수를 이진수로 보고 그 이진수 형태의 수들을 트라이에 넣어봅시다.

이제, 후보인 수들을 하나하나 선택하면서 XOR을 최대화하면 됩니다.

 

XOR을 최대화하는 건 현재 보고 있는 수와 정반대의 비트를 있는 대로 그리디하게 향하면 되며,

사전순 최소/최대 를 생각해보면 왜 그리디가 되는지는 자명합니다.

struct Nod{ int nxt[2] = {}; };
vector<Nod> tri;

int arr[100020];

void psh(int ni, const int& val, int idx){
	if (idx < 0){ return; }
	int nxi = val>>idx & 1;
	int& nxt = tri[ni].nxt[nxi];
	if (nxt == 0){
		nxt = tri.size(); tri.push_back( Nod() );
	}
	return psh(tri[ni].nxt[nxi], val, idx-1);
}

ll res = 0;
void qry(int ni, const int& val, int idx){
	if (idx < 0){ return; }
	int nxi = val>>idx & 1;
	if (tri[ni].nxt[1^nxi]){ res |= 1<<idx; return qry(tri[ni].nxt[1^nxi], val, idx-1); }
	else{ return qry(tri[ni].nxt[nxi], val, idx-1); }
}

void Main(){
	int n; cin >> n;
	tri.push_back( Nod() );
	for (int i = 1; i <= n; i++){ cin >> arr[i]; psh(0, arr[i], 30); }
	ll ans = 0;
	for (int i = 1; i <= n; i++){ res = 0; qry(0, arr[i], 30); ans = max(ans, res); }
	cout << ans;
}

6. [9250] 문자열 집합 판별 (Platinum II)

아호-코라식 구현 문제입니다.

struct Nod{ bool chk=0; int jmp=0; int nxt[30] = {}; };
vector<Nod> tri;
void psh(int ni, const string& s, int idx){ int sl = s.size();
	if (idx == sl){ tri[ni].chk = 1; return; }
	int nxi = s[idx]-'a';
	int& nxt = tri[ni].nxt[nxi];
	if (nxt == 0){
		nxt = tri.size(); tri.push_back( Nod() );
	}
	return psh(tri[ni].nxt[nxi], s, idx+1);
}
bool qry(const string& s){ int sl = s.size();
	int ptr = 0;
	for (int i = 0; i < sl; i++){
		int nxi = s[i]-'a';
		while (ptr != 0 && tri[ptr].nxt[nxi] == 0){ ptr = tri[ptr].jmp; }
		if (tri[ptr].nxt[nxi] != 0){ ptr = tri[ptr].nxt[nxi]; }
		if (tri[ptr].chk){ return 1; }
	}
	return 0;
}
void con(){
	queue<int> q; q.push(0);
	while (!q.empty()){
		int now = q.front(); q.pop();
		for (int nxi = 0; nxi < 26; nxi++){
			int nxt = tri[now].nxt[nxi]; if (nxt == 0){ continue; }
			if (now == 0){ tri[nxt].jmp = now; }
			else{
				int ptr = tri[now].jmp;
				while (ptr != 0 && tri[ptr].nxt[nxi] == 0){ ptr = tri[ptr].jmp; }
				if (tri[ptr].nxt[nxi] != 0){ ptr = tri[ptr].nxt[nxi]; }
				tri[nxt].jmp = ptr;
			}
			tri[nxt].chk |= tri[ tri[nxt].jmp ].chk;
			q.push(nxt);
		}
	}
}

void Main(){
	int n; cin >> n;
	tri.push_back( Nod() );
	while (n--){ string s; cin >> s; psh(0, s, 0); }
	con();
	int q; cin >> q;
	while (q--){
		string s; cin >> s; bool res = qry(s);
		if (res){ cout << "YES"; } else{ cout << "NO"; } cout << endl;
	}
}

7. [5905] 악당 로봇 (Platinum I)

아호 코라식 + DP 문제입니다.

입력받은 문자열로 아호 코라식을 일단 만든 뒤, 정점에서 탐색을 하면서 아래 DP를 돌려주면 됩니다.

$D{P}_{i,j}:=$ $j$번의 버튼을 누르고 $i$번 정점에 도착했을 때 할 수 있는 최대 공격 횟수

 

아호 코라식의 특성상 Failure Function을 언제든 타고 갈 수 있기 때문에, DP 전파를 다음 정점 뿐만 아니라 "현재 정점에서 Faliure Function을 타고 갈 수 있는 모든 정점"의 다음 정점 및 "시작 정점"에도 전파해줘야 합니다.

각 문자열의 길이가 짧기 때문에, 이걸 다 돌려줘도 시간 내에 여유롭게 통과합니다.

struct Nod{ int cnt=0; int jmp=0; int nxt[3] = {}; };
vector<Nod> tri;
void psh(int ni, const string& s, int idx){ int sl = s.size();
	if (idx == sl){ tri[ni].cnt += 1; return; }
	int nxi = s[idx]-'A';
	int& nxt = tri[ni].nxt[nxi];
	if (nxt == 0){
		nxt = tri.size(); tri.push_back( Nod() );
	}
	return psh(tri[ni].nxt[nxi], s, idx+1);
}
void con(){
	queue<int> q; q.push(0);
	while (!q.empty()){
		int now = q.front(); q.pop();
		for (int nxi = 0; nxi < 3; nxi++){
			int nxt = tri[now].nxt[nxi]; if (nxt == 0){ continue; }
			if (now == 0){ tri[nxt].jmp = now; }
			else{
				int ptr = tri[now].jmp;
				while (ptr != 0 && tri[ptr].nxt[nxi] == 0){ ptr = tri[ptr].jmp; }
				if (tri[ptr].nxt[nxi] != 0){ ptr = tri[ptr].nxt[nxi]; }
				tri[nxt].jmp = ptr;
			}
			tri[nxt].cnt += tri[ tri[nxt].jmp ].cnt;
			q.push(nxt);
		}
	}
}

int dp[1020][320];

void Main(){
	int n, k; cin >> n >> k;
	tri.push_back( Nod() );
	while (n--){ string s; cin >> s; psh(0, s, 0); }
	con(); int m = tri.size();
	memset(dp, -1, sizeof(dp)); dp[0][0] = 0;
	for (int i = 1; i <= k; i++){
		for (int j = 0; j < m; j++){
			if (dp[i-1][j] == -1){ continue; }
			int ptr = j;
			while (1){
				for (int nxi = 0; nxi < 3; nxi++){
					int nxt = tri[ptr].nxt[nxi];
					dp[i][nxt] = max(dp[i][nxt], dp[i-1][j] + tri[nxt].cnt);
				}
				if (ptr == 0){ break; }
				ptr = tri[ptr].jmp;
			}
			dp[i][0] = max(dp[i][0], dp[i-1][j]);
		}
	}
	int ans = 0;
	for (int j = 0; j < m; j++){ ans = max(ans, dp[k][j]); }
	cout << ans;
}

8. [3033] 가장 긴 문자열 (Platinum III)

LCP array를 구해주면, max(LCP[i])가 답이 됩니다.

 

max(LCP[i])가 lower_bound임은 자명하고 (lowest COMMON prefix), upper_bound임은 아래와 같이 증명할 수 있습니다.

• max(LCP[i])보다 더 큰 답이 존재한다면, 이 역시 Suffix Array에서 연속해야 하고, 그렇다면 LCP[i] > max(LCP[i])여야 하는데 이는 불가능하다.

int sa[200020], grp[200020], res[200020];
int pos[200020], lcp[200020];

int k, sl; string s;
bool cmp(int i1, int i2){
	if (grp[i1] != grp[i2]){ return grp[i1] < grp[i2]; }
	int p1 = i1+k, p2 = i2+k;
	if (p1 >= sl || p2 >= sl){ return p1 > p2; }
	return grp[p1] < grp[p2];
};

void Main(){
	cin >> sl >> s;
	for (int i = 0; i < sl; i++){ sa[i] = i; grp[i] = s[i]; }
	for (k = 1; ; k *= 2){
		sort(sa, sa+sl, cmp);
		res[0] = 0; for (int i = 1; i < sl; i++){
			if ( cmp(sa[i-1], sa[i]) ){ res[i] = res[i-1] + 1; }
			else{ res[i] = res[i-1]; }
		}
		for (int i = 0; i < sl; i++){ grp[ sa[i] ] = res[i]; }
		if (res[sl-1] == sl-1){ break; }
	}
	for (int i = 0; i < sl; i++){ pos[i] = grp[i]; }
	int k = 0;
	for (int i = 0; i < sl; i++){
		k -= 1; if (k < 0){ k = 0; }
		int i1 = pos[i], i2 = pos[i]-1;
		if (i2 < 0){ continue; }
		int p1 = sa[i1], p2 = sa[i2];
		while (p1+k < sl && p2+k < sl){
			if (s[p1+k] == s[p2+k]){ k += 1; }
			else{ break; }
		}
		lcp[ pos[i] ] = k;
	}
	cout << *max_element(lcp+1, lcp+sl);
}

9. [1605] 반복 부분문자열 (Platinum III)

"8. [3033] 가장 긴 문자열" 문제와 똑같습니다. 제한도 똑같습니다. 코드도 똑같습니다.

int sa[200020], grp[200020], res[200020];
int pos[200020], lcp[200020];

int k, sl; string s;
bool cmp(int i1, int i2){
	if (grp[i1] != grp[i2]){ return grp[i1] < grp[i2]; }
	int p1 = i1+k, p2 = i2+k;
	if (p1 >= sl || p2 >= sl){ return p1 > p2; }
	return grp[p1] < grp[p2];
};

void Main(){
	cin >> sl >> s;
	for (int i = 0; i < sl; i++){ sa[i] = i; grp[i] = s[i]; }
	for (k = 1; ; k *= 2){
		sort(sa, sa+sl, cmp);
		res[0] = 0; for (int i = 1; i < sl; i++){
			if ( cmp(sa[i-1], sa[i]) ){ res[i] = res[i-1] + 1; }
			else{ res[i] = res[i-1]; }
		}
		for (int i = 0; i < sl; i++){ grp[ sa[i] ] = res[i]; }
		if (res[sl-1] == sl-1){ break; }
	}
	for (int i = 0; i < sl; i++){ pos[i] = grp[i]; }
	int k = 0;
	for (int i = 0; i < sl; i++){
		k -= 1; if (k < 0){ k = 0; }
		int i1 = pos[i], i2 = pos[i]-1;
		if (i2 < 0){ continue; }
		int p1 = sa[i1], p2 = sa[i2];
		while (p1+k < sl && p2+k < sl){
			if (s[p1+k] == s[p2+k]){ k += 1; }
			else{ break; }
		}
		lcp[ pos[i] ] = k;
	}
	cout << *max_element(lcp+1, lcp+sl);
}

10. [9249] 최장 공통 부분 문자열 (Platinum III)

두 문자열을 (EOS 문자를 사이에 두고) 이어준 뒤, 한 문자열만 등장하는 Suffix와 그렇지 않은 Suffix의 LCP값 중 최댓값을 구해주면 됩니다.

TODO: 증명. 다만 직관적으로는 보이는 게, 한 쪽에서는 S1을, 다른 쪽에서는 S2를 잡은 뒤 LCP로 최댓값을 구해주는 방식임.

int sa[200020], grp[200020], res[200020];
int pos[200020], lcp[200020];

int k, sl; string s;
bool cmp(int i1, int i2){
	if (grp[i1] != grp[i2]){ return grp[i1] < grp[i2]; }
	int p1 = i1+k, p2 = i2+k;
	if (p1 >= sl || p2 >= sl){ return p1 > p2; }
	return grp[p1] < grp[p2];
};

void Main(){
	string s1, s2; cin >> s1 >> s2; int l1 = s1.size(), l2 = s2.size();
	s = s1 + "!" + s2; sl = s.size();
	for (int i = 0; i < sl; i++){ sa[i] = i; grp[i] = s[i]; }
	for (k = 1; ; k *= 2){
		sort(sa, sa+sl, cmp);
		res[0] = 0; for (int i = 1; i < sl; i++){
			if ( cmp(sa[i-1], sa[i]) ){ res[i] = res[i-1] + 1; }
			else{ res[i] = res[i-1]; }
		}
		for (int i = 0; i < sl; i++){ grp[ sa[i] ] = res[i]; }
		if (res[sl-1] == sl-1){ break; }
	}
	for (int i = 0; i < sl; i++){ pos[i] = grp[i]; }
	int k = 0;
	for (int i = 0; i < sl; i++){
		k -= 1; if (k < 0){ k = 0; }
		int i1 = pos[i], i2 = pos[i]-1;
		if (i2 < 0){ continue; }
		int p1 = sa[i1], p2 = sa[i2];
		while (p1+k < sl && p2+k < sl){
			if (s[p1+k] == s[p2+k]){ k += 1; }
			else{ break; }
		}
		lcp[ pos[i] ] = k;
	}
	int ans = 0, pos = 0;
	for (int i = 1; i < sl; i++){
		if ( (sa[i-1] < l1+1) ^ (sa[i] < l1+1) ){
			if (ans < lcp[i]){ ans = lcp[i]; pos = sa[i]; }
		}
	}
	cout << ans << endl;
	while (ans--){ cout << s[pos]; pos += 1; }
}

Not Solved

11. [3835] Alphabet Soup (Diamond V)

12. [20037] Bit String (Diamond V)

13. [6300] 단어 퍼즐 (Diamond V)