Codeforces Round #779 (Div. 2) 1541 → 1542

 

https://codeforces.com/contest/1656

Dashboard - CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

 

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

A. Marin and Photoshoot

https://codeforces.com/contest/1658/problem/A

Problem - A - Codeforces

문제

 

길이가 n인 string이 주어진다. 0과 1로 이루어져 있고 0은 male , 1은 female이다. 어떠한 string이 길이가 2인 이상의 연속된 부분의 male의 개수가 female을 초과하지 않는다면 beautiful이라고 불린다. 입력받은 string에서 임의의 원소를 추가하여 beautiful을 만들 수 있는 최소 추가 개수를 출력하는 문제

 

풀이

 

주어진 입력에 00이 있으면 0110을 만들어 주어야 해서 2개를 추가하고 010이 있으면 0110을 만들어줘야하기 때문에

1개를 추가해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    string s;
    vector<pair<int,int>> v;
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		v.clear();
    		int n;
    		string s;
    		cin >> n >> s;
    		int ans = 0;
    		for (int i = 1; i < n; i++) {
    			if (s[i] == '0' && s[i] == s[i - 1]) {
    				ans += 2;
    			}
    		}
    		for (int i = 0; i < n; i++) {
    			if (s[i] == '0') {
    				int start = i, end = i + 1;
    				while (end < n) {
    					if (s[end] == '0')end++;
    					else break;
    				}
    				end--;
    				v.push_back({ start,end });
    				i = end;
    			}
    		}
    		for (int i = 1; i < v.size(); i++) {
    			if ((v[i].first - v[i - 1].second) == 2) {
    				ans++;
    			}
    		}
    		cout << ans << '\n';
    	}
     
     
    }

 

B. Marin and Anti-coprime Permutation

https://codeforces.com/contest/1658/problem/B

Problem - B - Codeforces

 

문제

 

어떠한 permutation이 만약 gcd(p[1]*1,p[2]*2,p[3]*3..p[n]*n) > 1 을 만족한다면 beautiful이라고 하고 길이가 n인 beautiful한 permutation의 개수를 출력하는 문제

 

풀이

 

주어진 수에서 홀수는 2의 배수가 아니기 때문에 다른 짝수 모든 짝수를 홀수로 만들 수 없다고 생각했고, 결국 홀수를 모두 짝수로 바꿔주는 방법을 생각했다. 이는 n이 홀수일때 홀수가 1개더 많아서 답은 무조건 0이고 이외에는 n/2길이의 원소를 배치하는 경우의수가 2개인 factorial[n/2]*factorial[n/2]를 출력해주면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long fact[1001];
    const long long mod = 998244353;
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	fact[1] = 1;
    	for (long long i = 2; i <= 1000; i++) {
    		fact[i] = fact[i - 1] * i;
    		fact[i] %= mod;
    	}
    	int T;
    	cin >> T;
    	while (T--) {
    		int n;
    		cin >> n;
    		if (n % 2)cout << "0\n";
    		else {
    			long long ans = fact[n / 2] * fact[n / 2];
    			ans %= mod;
    			cout << ans << '\n';
    		}
    	}
     
     
    }

D1. 388535 (Easy Version)

https://codeforces.com/contest/1658/problem/D1

Problem - D1 - Codeforces

 

문제

 

l과 r이 주어진다. l과 r사이의 수로 이루어진 permutation에 대해서 모든 원소에 임의의 수 x를 xor 시킨 값이 입력으로 주어지는데 x를 찾아내는 문제

 

풀이

 

원래 permuation의 각 비트 자리수마다 개수를 세고, 입력받은 배열의 각 비트 자리수마다 개수를 세서  비트 자리수가 다르다면 1, 같으면 0을 추가해줘서 출력해주면 된다.

 

코드

    #include <bits/stdc++.h>
    using namespace std;
    long long a[400001];
    int cnt[100],ocnt[100];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
    	int T;
    	cin >> T;
    	while (T--) {
    		for (int i = 0; i < 20; i++) {
    			cnt[i] = 0;
    			ocnt[i] = 0;
    		}
    		long long l, r;
    		cin >> l >> r;
    		for (int i = l; i <= r; i++) {
    			for (int j = 0; j < 20; j++) {
    				if ((i & (1 << j))) {
    					ocnt[j]++;
    				}
    			}
    		}
    		long long dif = r - l + 1;
    		long long ans = 0;
    		for (int i = 0; i < dif; i++) {
    			cin >> a[i];
    			for (int j = 0; j < 20; j++) {
    				if ((a[i] & (1 << j))) {
    					cnt[j]++;
    				}
    			}
    		}
    		for (int i = 0; i < 20; i++) {
    			if (ocnt[i] != cnt[i]) {
    				ans += (1 << i);
    			}
    		}
    		cout << ans << '\n';
    	}
     
     
    }

 

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.