[CF] Round #769 (Div. 2) _ 220130

https://codeforces.com/contest/1632

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

 

하아

조졌네

그치만 오히려 좋아

정신 차리자

 

 

A.

개인적으로 palindrome을 좋아한다.

좋아해서 신나게 풀었다.

bool palin(const string& s, int start, int end) {
	if (start > end) {
		return true;
	}
	else {
		if (s[start] != s[end]) {
			return false;
		}
		return palin(s, start + 1, end - 1);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n; string s; cin >> s;
		bool ans = true;
		for (int i = 0; i < n && ans; ++i) {
			for (int j = i + 1; j < n && ans; ++j) {
				if (palin(s, i, j)) {
					ans = false;
					break;
				}
			}
		}
		cout << (ans ? "YES" : "NO") << kEndl;
	}
}

 

 

B.

작년 겨울 SUAPC 때

https://www.acmicpc.net/problem/20941

20941번: 성싶당

이 문제를 풀고 Gray Code를 알게 됐다.

B번 문제를 읽자마자 이런 느낌이라는 건 알았는데 뭔가 잘 안됐다.

예를 들어 처음에는 0 -> 1 -> 3 -> 2 이런 식으로 가는 걸 생각했는데 당장 n이 3일 때 1 -> 3 -> 2가 불가능했고, 이걸 해결하기 위해 그냥 1 -> 2로 가자니 튀는 부분이 발생한다.

온갖 방법으로 다 접근하다가 그냥 n - 1부터 시작해서 가장 높은 비트부터 바꿔주면서 내려오면 된다는 걸 깨달았다.

웰노운인 거 같다. 당연하게도?

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n;
		vector<bool> chk(n, false);
		vector<int> ans;

		int cur = n - 1;
		chk[cur] = true; ans.push_back(cur);
		while (ans.size() < n) {
			for (int for_xor = 1 << 18; for_xor > 0; for_xor /= 2) {
				int next = cur ^ for_xor;
				if (next >= n) {
					continue;
				}
				if (!chk[next]) {
					chk[next] = true;
					cur = next;
					ans.push_back(cur);
					break;
				}
			}
		}

		for (const int& num : ans) {
			cout << num << ' ';
		}
		cout << kEndl;
	}
}

 

C.

결국 못 풀었다.

그렇지만 일단 잘 거다. 내일 하루가 바쁘기 때문에...

 

 

아직 system testing도 안 끝났는데,,, 제발 살려주세요.