Codeforces Round #742 (Div. 2) , 1484 -> 1424 (-60)

 

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

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

 

 

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

 

A. Domino Disaster

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

1 x 2 도미노로 2행 n 열을 꽉 채우는 문제
도미노는 옆으로 기울 수 있다.

 

풀이

 

입력 값이 L이면 L, R이면 R, D이면 U, U이면 D 를 출력 해주면 된다. 

 

코드

 

#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;
		string s;
		cin >> n >> s;
		for (int i = 0; i < n; i++) {
			if (s[i] == 'L')cout << 'L';
			if (s[i] == 'R')cout << 'R';
			if (s[i] == 'U')cout << 'D';
			if (s[i] == 'D')cout << 'U';
		}
		cout << '\n';
	}
}

 

B. MEXor Mixup

Problem - B - Codeforces

Problem - B - Codeforces

문제

 

숫자 a , b가 주어졌을때, 모든 배열 원소의 MEX가 a, 모든 배열 원소의 XOR이 b가 나오는 최소 배열의 길이

를 구하는 문제

 

풀이

 

1부터 a-1까지 모든 원소를 XOR 시키면 MEX는 a가 된다. 이때 XOR시킨 값을 X라고 했을 때,

X = b이면 바로 a를 출력 (0~a-1)개

X != b일때, X=a 이면 a+2,  x != a 이면 a+1 을 출력해주면 된다. 

다만 이때 0~30만까지의 XOR을 미리 구해놓아야 시간 초과가 뜨지 않는다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long d[300001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for (int i = 1; i < 300001; i++) {
		d[i] = d[i - 1] ^ i;
	}
	int T;
	cin >> T;
	while (T--) {
		long long a, b, start = 0, next = 0, start2 = 1,sum=0;
		cin >> a >> b;
		start = d[a - 1];
		for (long long i = 0; i < 30; i++) {
			int k = (1 << i);
			if ((start & k) != (b & k))sum += start2;
			start2 *= 2LL;
		}
		if (b == start) {
			cout << a << '\n';
			continue;
		}
		if (a == sum)cout << a + 2 << '\n';
		else cout << a + 1 << '\n';
	}
}

 

레이팅 변화 : 

1484 -> 1424 (-60)

 

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

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