[2022.11.06. 팀연습] ICPC Seoul Regional 2020 본선 후기

경과

타임라인	문제	킬	어시스트
10분	[B] Commemorative Dice	pizzaroot
적을 처치했습니다!
32분	[C] Dessert Café	WA
38분		WA
연속 킬 차단!
48분	[E] Imprecise Computer	pizzaroot
더블 킬!
58분	[C] Dessert Café	WA
71분		WA
78분		WA
제압 되었습니다!
98분	[J] Switches	WA
108분	[C] Dessert Café	wlsth1004100	3juhwan
아군이 적을 처치했습니다!
116분	[J] Switches	pizzaroot
트리플 킬!
160분	[G] Mobile Robot	WA
174분		pizzaroot	3juhwan / wlsth1004100
쿼드라 킬!

 

풀이

[B] Commemorative Dice

 

가능한 36가지를 모두 체크하면서 세주면 된다. 기약분수로 출력한다.

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	vector<int> d1(6), d2(6);
	for (auto &x : d1) cin >> x;
	for (auto &x : d2) cin >> x;
	int win = 0;
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			if (d1[i] > d2[j]) win++;
		}
	}
	int denom = 36;
	int g = __gcd(win, denom);
	cout << win / g << "/" << 36 / g << "\n";
	return 0;
}

 

[E] Imprecise Computer

 

모두 0인 상태에서 시작해서 이웃한 두 원소 마다 하나는 -1, 하나는 +1하는 작업을 최대 한번했을 때 만들수 있는 결과인지 확인하는 것과 같다. 따라서 거꾸로 작업했을 때 그리디하게 왼쪽에서부터 처리해준후 모두 0이 되는지 확인해주면 된다.

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; vector<int> d(n);
	for (auto &x : d) cin >> x;
	for (int i = 1; i < n; i++) {
		if (d[i - 1] > 1) { cout << "NO\n"; return 0; }
		if (d[i - 1] == 1) {
			if (d[i]) d[i]--;
			else d[i]++;
		}
	}
	if (d[n - 1]) cout << "NO\n";
	else cout << "YES\n";
	return 0;
}

 

[G] Mobile Robot

 

이분탐색? 삼분탐색? 등을 떠올렸지만 생각해보면 현재 상태와 원하는 상태의 차이를 계산한 뒤, 차이들의 최대와 최소의 차이를 구해주면 된다. 그런데 함정은 역정렬도 가능하기때문에 두방향 중 최소인 것을 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll n, d; cin >> n >> d; vector<ll> a(n), diff(n), diff2(n);
	for (auto &x : a) cin >> x;
	for (ll i = 0; i < n; i++) {
		diff[i] = a[i] - a[0] - d * i;
	}
	reverse(a.begin(), a.end());
	for (ll i = 0; i < n; i++) {
		diff2[i] = a[i] - a[0] - d * i;
	}
	ll ans = *max_element(diff.begin(), diff.end()) - *min_element(diff.begin(), diff.end());
	ans = min(ans, *max_element(diff2.begin(), diff2.end()) - *min_element(diff2.begin(), diff2.end()));
	cout << ans / 2 << ".";
	if (ans & 1) cout << "5\n";
	else cout << "0\n";
	return 0;
}

 

[J] Switches

 

역행렬 구하는 비슷한 느낌으로 XOR연산으로 가우스 소거법을 진행하고 행별로 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; vector<vector<int>> omat(n, vector<int>(n, 0)), imat(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		imat[i][i] = 1;
		for (int j = 0; j < n; j++) {
			cin >> omat[i][j];
		}
	}
	for (int j = 0; j < n; j++) {
		bool good = false;
		for (int f = j; f < n; f++) {
			if (omat[f][j]) {
				for (int k = 0; k < n; k++) {
					swap(omat[f][k], omat[j][k]);
					swap(imat[f][k], imat[j][k]);
				}
				good = true;
				break;
			}
		}
		if (!good) { cout << "-1\n"; return 0; }
		for (int i = 0; i < n; i++) {
			if (i == j) continue;
			if (omat[i][j]) {
				for (int k = 0; k < n; k++) {
					omat[i][k] ^= omat[j][k];
					imat[i][k] ^= imat[j][k];
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (imat[i][j]) cout << j + 1 << " ";
		}
		cout << "\n";
	}
	return 0;
}

 

후기

문제도 본선치고는 쉬운 편이였던것 같고 운도 좋았던 것 같다. 많이 풀어서 기분은 좋았다.