Codeforces Round #770 (Div. 2)

오늘 AI가 코포에 참여한다고 들어서 긴장되는(?) 마음으로 코포에 참여했다. 근데 오늘 참여 안 했다고 한다ㅠㅠ.

 

담에 보자 AI쉑..

 

 

민트에 올라온 후 첫 코포였다.

 

저번에 민트를 찍고 뭔가 떨어질 것 같았다. 그래서 부캐를 파서 한 번 돌렸었다.

근데 djs100201가 뭔 민트 박제냐고 그냥 박으라해서 박았다.

 

다행히 오늘도 3솔로 민트를 유지할 수 있게 되었다!

아니 심지어 점수가 많이 오른다. ㄷㄷ

 

최근 학회 버츄얼 스터디를 포함하여 3연 3솔에 성공했다. 

기분이 되게 좋다. 오예.

 

아 그리고 최근에 학교선배 블로그(https://rebro.kr/72)에서

이런 팁을 봤었는데, 이거 덕분에 오늘 안 말리고 잘 볼 수 있었던 것 같다! 감사합니다~

B넘기고 C먼저 푼 게 아주 좋았다.

 

---

 

A.

우선 당연하게도 k가 0이면 답은 1이다.

자 이제, 한 번 만들어보자. 그니까 s+rev(s)랑 rev(s)+s를 만들어보자. 이 두 개가 같으면 k가 몇이든 답이 1이다.

그 외에는 답이 무조건 2이다. 몇 개를 해보면 바로 알 수 있다.

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n, k;
string s;

void solve() {
	cin >> n >> k;
	cin >> s;
	if (k == 0) {
		cout << 1 << endl;
		return;
	}
	string x, y, rev;
	rev = s;
	reverse(rev.begin(), rev.end());
	x = s + rev;
	y = rev + s;
	if (x == y) cout << 1 << endl;
	else cout << 2 << endl;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	while (tc--) solve();
	return 0;
}

 

B.

되게 신선한? 문제였다. 감을 못 잡고 한참 헤맸다. 푼 사람 수를 보니 B랑 C가 1000명도 차이 나지 않았어서 C로 넘어갔다가 C를 풀고 다시 돌아와서 풀었다.

 

이거 딱 풀어내는 순간 진짜 기분이 좋았다.

사고과정이 생생하니 적어보자.

 

왜 답이 항상 존재하는 걸까? -> 2^n개의 경우의 수가 있을 텐데 답이 항상 존재하는 경우만 있다고 하는 걸 보면 2^n개의 경우의 수를 따질 이유가 없을 것이라고 생각.

그럼 그리디일까? -> 그런 성질을 찾을 수가 없음

그렇다면 왜 x와 x+3을 줬을까? -> 설마 홀짝?

어? +와 xor의 특성상 두 수의 결과값의 홀짝은 항상 정해져 있네?

오 그러면 Alice기준으로 1부터 n까지 연산을 쭉 하고 나면 홀수인지 짝수인지 정해지겠구나!

y값이 홀수 아니면 짝수이고, 답이 항상 하나만(앨리스 or 밥) 존재한다고 했으므로 최종 값의 홀짝을 쉽게 구할 수 있다.

그 값이 y값의 홀짝과 같으면 Alice, 다르면 Bob을 출력하면 된다.

 

+연산과 xor연산은 한 번도 필요가 없다 ㅋㅋ

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n, x, y;

void solve() {
	cin >> n >> x >> y;
	vector<ll> a(n + 1);
	for (ll i = 1; i <= n; i++) cin >> a[i];

	//앨리스기준으로 보자.
	bool e = true; //짝수면 true 홀수면 false
	if (x % 2 == 1) e = false;

	for (ll i = 1; i <= n; i++) {
		if (e) {//지금 짝수
			if (a[i] % 2) e = false; //홀수
			else continue;
		}
		else {//지금 홀수
			if (a[i] % 2) e = true;
			else continue;
		}
	}
	if (e) {//짝
		if (y % 2 == 1) cout << "Bob" << endl;
		else cout << "Alice" << endl;
	}
	else {//홀
		if (y % 2 == 1) cout << "Alice" << endl;
		else cout << "Bob" << endl;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	while (tc--) solve();
	return 0;
}

 

 

C.

나는 C가 B보다 훨~~씬 쉬웠다.

실제로 C를 푼 사람이 B를 푼 사람보다 3800명이나 많다.

 

문제를 요약하면 다음과 같다.

n*k크기의 행렬이 있다. 1부터 n*k까지의 수를 배치해야 한다. 이때 조건이 있다.

어떤 행의 연속된 부분을 골라도 그 부분의 평균이 소수가 아닌 정수가 되게 하면 된다.

 

같은 행의 수들은 모두 짝수로 이루어지거나, 모두 홀수로 이루어져 있어야 한다. 그래야 조건을 만족함.

 

따라서 n*k가 짝수여야 한다. 또한, (짝수의 개수)%(열의 크기)==0이어야 한다. 그렇지 않다면 어떤 한 줄은 홀, 짝이 모두 들어가게 된다.

 

n==1, k==1일 때 예외처리도 잘 해주자.

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 1000000007
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll n, k;

void solve() {
	cin >> n >> k;
	if (n == 1) {
		if (k == 1) {
			cout << "YES" << endl;
			cout << 1 << endl;
		}
		else cout << "NO" << endl;
		return;
	}
	if (k == 1) {
		cout << "YES" << endl;
		for (ll i = 1; i <= n; i++) cout << i << endl;
		return;
	}
	if ((n * k) % 2 != 0) {
		cout << "NO" << endl;
		return;
	}
	if ((n * k / 2) % k != 0) {
		cout << "NO" << endl;
		return;
	}
	cout << "YES" << endl;
	ll now = 1;
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= k; j++) {
			cout << now << ' ';
			now += 2;
		}
		if (now > n * k) now = 2;
		cout << endl;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	while (tc--) solve();
	return 0;
}

 

 

 

흐름을 탄 거면 좋겠다. 화이팅!