Educational Codeforces Round #139 (Div 2.)

 

 

https://codeforces.com/contest/1766

Dashboard - Educational Codeforces Round 139 (Rated for Div. 2) - Codeforces

 

 

 

A. Extremely Round

 

 

요약

 

 

수를 구성하는 자릿수 중 0이 아닌 수를 단 하나만 가지는 양수의 개수를 구한다.

---

1. 1 ~ 9, 10 ~ 99, 100 ~ 999 ...로 딱 떨어지는 수를 센 뒤 더해주는 방식을 택한다.

 

2. 한 자릿수마다 조건에 부합하는 수는 9개이다.

#include <bits/stdc++.h>
using namespace std;

int t, N;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		cin >> N;
		int ans = 0;
		while (N) {
			if (N >= 10) ans += 9;
			else ans += N;
			N /= 10;
		}
		cout << ans << '\n';
	}
	return 0;
}

 

 

 

B. Notepad#

 

 

요약

 

길이 n의 문자열을 입력하고자 한다. 두 가지 행동을 할 수 있을 때, n번보다 작은 횟수로 문자열을 입력할 수 있는지 알아본다.

---

1. 다음 두 가지 행동을 진행할 수 있다.

첫 째, 아무 문자를 문자열 끝에 추가한다.

둘 째, 이미 입력한 문자열 중 continuous한 substring을 복사하여 문자열의 끝에 추가한다.

 

2.  길이가 최소 2인 continuous한 substring에 대하여 두 번째 행동을 한 번이라도 진행할 수 있다면, n번보다 작은 실행으로 길이가 n인 문자열을 입력할 수 있다.

 

3. 두 번째 행동을 진행할 수 있는지 확인하기 위해 현재까지 나온 문자열 중 길이가 2인 substring을 모두 set에 저장하고, 앞으로 나올 두 문자와 비교하여 정답을 출력한다.

#include <bits/stdc++.h>
using namespace std;

int t, N;
string S;
set <string> s;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		int flag = 0;
		cin >> N;
		cin >> S;
		s.clear();
		for (int i = 1; i < N - 2; i++) {			
			string input = "", cmp = "";
			input += S[i - 1]; input += S[i];
			cmp += S[i + 1]; cmp += S[i + 2];
			s.insert({ input });
			if (s.count({ cmp })) flag = 1;			
		}
		if (flag == 1) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

 

 

 

C. Hamiltonian Wall

 

 

요약

 

원래 전부 W였던 벽을 B로 한붓그리기로 칠하여 제시된 벽으로 바꿀 수 있는지 여부를 확인한다.

---

1. 벽은 2행 M열로 주어진다. greedy하게 생각해 보면, 현재 열을 다 칠하지 못하고 다음 열로 넘어가게 되면 벽을 한붓그리기로 칠할 수 없게 된다.

 

2. 백트래킹 기법을 활용하여 현재 열의 벽이 다 칠해지지 않았으면 위 혹은 아래로, 다 칠해져있다면 오른쪽으로 이동하며 벽을 칠할 수 있는지를 확인한다.

#include <bits/stdc++.h>
using namespace std;

int t, M, flag;
string wall[2];

void BackTracking(int x, int y);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> t;
	while (t--) {
		flag = 0;
		cin >> M;
		for (int i = 0; i < 2; i++) cin >> wall[i];
		BackTracking(0, 0);
		BackTracking(0, 1);
		if (flag == 1) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

void BackTracking(int x, int y) {
	if (x == M) {
		flag = 1;
		return;
	}
	else {
		if (wall[y][x] == 'W') return;
		wall[y][x] = 'W';
		if (wall[y ^ 1][x] == 'B') BackTracking(x, y ^ 1);
		else BackTracking(x + 1, y);
		wall[y][x] = 'B';
	}
}

 

 

 

D. Lucky Chains

 

 

요약

 

정수 A와 B가 주어졌을 때, (A,B), (A+1,B+1), (A+2,B+2) ... (A+k, B+k)가 모두 서로소가 되도록 하는 k의 최대값을 구한다.

---

1. 정답은 크게 세 가지로 나뉜다.

첫 째, 이미 A와 B가 서로소가 아닌 경우 k = 0

둘 째, 모든 k에 대하여 A와 B가 서로소인 경우, k = INF. 이 경우는 A와 B의 차이가 오직 1일때만 발생한다.

셋 째, 정수 k가 존재하는 경우.

 

2. 첫 째와 둘 째 경우는 A와 B를 입력 받은 후 판단하고, 셋 째 경우일 때를 생각해보자.

B - A를 delta라고 하였을 때, (A+k, B+k)는 언젠가 반드시 delta의 배수가 된다. 조금 더 확장하여 생각해보면, (A+k, B+k)는 언젠가 반드시 delta가 가지는 소인수들의 배수가 됨을 떠올릴 수 있다.

 

3. delta의 소인수 중 하나를 prime이라고 할 때, k의 후보는 prime - (A % prime)이 된다. delta를 소인수 분해하며 prime - (A % prime)의 최소값을 구한다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int N, A, B;
int table[10001];
vector <int> primeNum;

int GCD(int a, int b) {
	if (a > b) {
		if (a % b == 0) return b;
		else return GCD(a % b, b);
	}
	else {
		if (b % a == 0) return a;
		else return GCD(b % a, a);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 2; i <= 10000; i++) {
		if (table[i] == 0) {
			primeNum.push_back(i);
			for (int j = i * i; j <= 10000; j += i) table[j] = 1;
		}
	}
	cin >> N;
	while (N--) {
		cin >> A >> B;
		int ans = INF;
		if (GCD(A, B) != 1) {
			cout << 0 << '\n';
			continue;
		}
		int delt = B - A;
		if (delt == 1) {
			cout << -1 << '\n';
			continue;
		}
		for (int i = 0; i < primeNum.size(); i++) {
			int now = primeNum[i];
			if (now > delt) break;
			if (delt % now == 0) {
				ans = min(ans, now - (A % now));
				while (1) {
					if (delt % now == 0) delt /= now;
					else break;
				}
			}
		}
		if(delt != 1) ans = min(ans, delt - (A % delt));
		cout << ans << '\n';
	}
	return 0;
}

 

 

 

 

E. Decomposition

 

 

요약

 

Decomposition의 정의가 주어진다. $\sum_{i=1}^{n}\sum_{j=1}^{n}f(a\left [ i..j \right ])$를 구하여라.

---

1. 0, 1, 2, 3으로만 이루어진 수열 $\left [ x_1, x_2, ... x_n \right ]$이 주어졌을 때, subarray를 형성한다. subarray의 마지막 원소와 $x_i$를 bitwise AND 연산한 값이 0보다 크다면, 그 원소를 subarray의 마지막에 추가하고, 아니면 다음 subarray를 고려한다. 그러한 subarray가 존재하지 않으면 $x_i$ 하나로 이루어진 subarray를 생성한다. $f(a\left [ i..j \right ])$는 i부터 j까지 decomposition을 진행하였을 때, subarray의 개수를 의미한다.

 

2. DP로 풀이한다. 만약 수열이 1, 2, 3으로만 이루어져 있다고 생각했을 때, subarray의 개수는 3개를 넘지 않는다. 따라서 map을 활용하여 table을 구성한다. table[i][state]를 i번째 원소에서 state 상태로 시작하였을 때, subarray의 개수로 구성한다. state은 size가 최대 3인 vector이다. 수열에 0이 포함되어 있을 때, state에는 변화가 없고 단순히 subarray의 개수가 1 늘어남을 알 수 있다.

#include <bits/stdc++.h>
using namespace std;

int N;
long long ans;
int arr[300000];
map <vector<int>, long long> table[300000];

long long DP(int now, vector<int> state);
pair <vector<int>, long long> calc(int now, vector<int> state);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N; i++) ans += DP(i, vector<int>(0));
	cout << ans;
	return 0;
}

long long DP(int now, vector<int> state) {
	if (now == N) return 0;
	if (table[now].count(state)) return table[now][state];
	auto p = calc(now, state);
	table[now][state] = p.second * (N - now) + DP(now + 1, p.first);
	return table[now][state];
}

pair <vector<int>, long long> calc(int now, vector<int> state) {
	if (arr[now] == 0) return { state, 1 };
	for (int i = 0; i < state.size(); i++) {
		if (arr[now] & state[i]) {
			state[i] = arr[now];
			return { state, 0 };
		}
	}
	state.push_back(arr[now]);
	return { state, 1 };
}