Codeforces Round #769 (Div. 2) 1678 -> 1654

https://codeforces.com/contest/1632

Dashboard - Codeforces Round #769 (Div. 2) - Codeforces

 

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

 

A. ABC

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

Problem - A - Codeforces

문제

 

0 과 1로만 이루어진 문자열이 있다. 주어진 문자열을 원하는대로 재정렬하여 길이가 2이상인 팰린드롬이 없게 만들 수 있는지 출력하는 문제

 

풀이

 

0이든 1이든 같은 문자가 2개이상 있으면 정답은 NO 이외에는 YES이다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n;
    		cin >> n;
    		string s;
    		cin >> s;
    		int cnt0 = 0, cnt1 = 0;
    		for (int i = 0; i < n; i++) {
    			if (s[i] == '0')cnt0++;
    			else cnt1++;
    		}
    		if (cnt0 > 1 || cnt1 > 1)cout << "NO\n";
    		else cout << "YES\n";
    	}
    }

 

 

B. Roof Construction

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

Problem - B - Codeforces

문제

 

0 부터 n-1까지의 수가 있다. 모두 xor 시켰을때 최소 값이 나오도록 수를 임의의 순서로 정렬하여 출력하는 문제

 

풀이

 

모두 xor 시켰을때 결국 n-1보다 같거나 작은 2의 제곱수가 최소 값이 된다. 그렇게 정렬하려면 {n-1 , ... , 최대 2의제곱수 , 0,  ... , 나머지 자유롭게 } 순으로 정렬하면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    bool check[200001];
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	int T;
    	cin >> T;
    	while (T--) {
    		int n;
    		cin >> n;
    		if (n == 2)cout << "0 1\n";
    		else if (n == 3)cout << "2 0 1\n";
    		else {
    			int cnt = 0, start = 1;
    			while (start <= (n-1))start *= 2;
    			start /= 2;
    			for (int i = n - 1; i >= start; i--)cout << i << ' ';
    			cout << 0 << ' ';
    			for (int i = start - 1; i > 0; i--)cout << i << ' ';
    			cout << '\n';
    		}
    	}
    }

C. Strange Test

https://codeforces.com/contest/1632/problem/C

Problem - C - Codeforces

문제

 

두 수 a,b가 주어졌을때 아래 연산을 통해 a를 b로 만들 수 있는 최소 연산의 수를 출력하는 문제

1. a+=1

2. b+=1

3. a|=b

 

풀이

 

a부터 b까지 모든 a를 더해가면서 , a를 b bit에 맞게 더한 후 or시킨 값과 , b를 a bit에 맞게 더한 후 or 시킨 값의 최소를 저장해 출력한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    int d[23];
    const int MAX = 3000000;
    int main() {
    	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    	d[0] = 1;
    	for (int i = 1; i < 23; i++)d[i] = d[i - 1] * 2;
    	int T;
    	cin >> T;
    	while (T--) {
    		int a, b;
    		cin >> a >> b;
     
    		int ans = MAX,sum=0;
    		while (true) {
    			if (a == b)break;
    			if ((a + 1) == b) {
    				ans = min(ans, sum + 1);
    				break;
    			}
    			bool flag = true;
    			for (int i = 19; i >= 0; i--) {
    				if ( (a & d[i]) && (b & d[i])==0) {
    					flag = false;
    					break;
    				}
    			}
    			if (flag) {
    				ans = min(ans, sum + 1);
    			}
    			ans = min(ans, sum + b - a);
    			int t1=MAX, t2 = MAX;
    			int tempB = b,tempA=a;
    			//b에 더해준다
    			for (int i = 19; i >= 0; i--) {
    				if ((tempB & d[i]) && (tempA & d[i]) == 0) {
    					tempB -= d[i];
    				}
    				else if ((tempA & d[i]) && (tempB & d[i])) {
    					tempA -= d[i];
    					tempB -= d[i];
    				}
    				else if ((tempA & d[i]) && (tempB & d[i])==0) {
    					t2 = tempA - tempB;
    					break;
    				}
    			}
    			//a에 더해준다
    			tempA = a; tempB = b;
    			for (int i = 19; i >= 0; i--) {
    				if ((a & d[i]) && (b & d[i])) {
    					tempA -= d[i];
    					tempB -= d[i];
    				}
    				else if ((a & d[i]) == 0 && (b & d[i])) {
    					t1 = d[i] - tempA;
    					break;
    				}
    			}
    			if (a + t1 == b) ans = min(ans, sum + t1);
    			else ans = min(ans, sum + t1 + 1);
    			ans = min(ans, sum + t2 + 1);
    			a++;
    			sum++;
    		}
    		cout << ans << '\n';
    	}
    }

 

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

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