Codeforces Round #439 Div.2 참가 후기

이번 코드포스 콘테스트는 Division 2만 개최되었다. Div1에 해당하는 사람도 참가는 가능하지만, competition은 Div2에 해당하는 사람만 이루어졌다.

풀지 못한 문제도 대회가 끝난 후 읽어보고 Editorial을 읽으면서 계속 공부하려고 해 보았는데, 오랜만에 제대로 공부하는 느낌이 드는 대회였다.

A번 문제

http://codeforces.com/contest/869/problem/A

하나하나 실제로 시뮬레이션 하면 된다. 이미 한번 나왔던 수 인지는 unordered_set으로 확인했다. 그런데 대회가 끝난 후 editorial을 읽어보니, 수학적 증명에 따라서 무조건 짝수개가 나온다고 한다. xor의 수학적 특징때문이다. A xor B = C라면 B xor C = A이라는 뭐 이런 특징때문이라고 한다. A번 문제 쉽다고 생각해서 그냥 풀어버리고 나왔는데, 생각보다 신박한 부분이 있다.

문제가 xi와 yi를 xor한 값이, 2n개의 배열, x1, x2, x3... xn, y1, y2, ... yn의 총 2n개의 배열 안에 들어있으면 카운트를 센다는 것인데, xor한 값이 2n보다 작은지라고 문제를 잘못 이해해서 hack 당한 사람들이 몇 명 있었다.

#include <iostream>
#include <unordered_set>
using namespace std;

int arr[2002][2];
unordered_set<int> s;
int main() {
	int n;
	cin >> n;
	for (int i=0;i < 2; i ++) {
		for (int j=0; j< n; j++) {
			cin >> arr[j][i];
			s.insert(arr[j][i]);
		}
	}
	
	bool even = true;
	for (int i=0; i < n; i++) {
		for (int j=0; j < n; j++) {
			auto& xi = arr[i][0];
			auto& yi = arr[j][1];
			int val = (xi ^ yi);
			if (s.find(val) != s.end()) {
				even = !even;
			}
		}
	}
	
	cout << (even ? "Karen" : "Koyomi") << endl;
}

B번 문제

http://codeforces.com/contest/869/problem/B

죄다 곱해버리면 될 것 같은데, 수가 커서 TLE가 나온다. 그런데 여기서 어차피 마지막 decimal digit을 구할 것이므로, 1의자리수만 고려하면 될 것 같다. 10번마다 주기적으로 회전하므로, 이를 고려하면 된다는 것! 그런데 또 보면 10번을 돈다는 것은, 0이 포함되므로 그냥 0이 나온다는 것이다. 따라서 a와 b의 차이값이 10이상이면 무조건 0이다.    

코드를 잘못 내서 hack 당했다.. 중간에 주석처리한 부분을 주석을 해제하면 Hack당한 코드가 된다. 주석 처리해서 지금은 Accept 판정을 받은 코드이다.

#include <iostream>

typedef long long ll;
using namespace std;

int main() {
	ll a, b, ans;
	cin >> a >> b;
	if (b-a >= 10) {
		cout << 0 << endl;
		return 0;
	}
	ans = 1;
	// b %= 10;
	// a %= 10;
	for (ll k = b; k > a; k--) {
		ans *= k;
		ans %= 10;
	}
	cout << ans << endl;
}

C번 문제

http://codeforces.com/contest/869/problem/C

섬 a,b,c에 대하여, a-b, b-c, c-a 연결 시 다리 개수는 모두 독립적이다. a-b 연결 다리 개수는 다리가 0개일때, 1개일때, ... n개일때 모두 고려해서 더하면 된다. n개는 min(a,b) 개이며, a와 b의 섬 개수 중 최소값이다. 다리가 i개 일때는 aCi * bCi * i!의 개수가 나오게 된다. 연결에 참여할 섬들을 고른 뒤 어떻게 연결할 것인지를 곱한 값이다. 팩토리얼과 이항계수는 dp로 구현했다. 메모리가 아슬아슬하다.

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353

typedef long long ll;

int dp[5001][5001];
int bicof[5001][5001];
int facto[5001];

ll get_facto(int n) {
	if (n <= 1) {
		return 1;
	}
	if (facto[n]) return facto[n];
	ll ret = 1;
	return facto[n] = (n * get_facto(n-1)) % MOD;
}

ll pascal(int n, int r) {
	if (n==r) return 1;
	if (n==0 || r==0) return 1;
	if (bicof[n][r]) return bicof[n][r];
	return bicof[n][r] = ((ll)pascal(n-1, r) + (ll)pascal(n-1, r-1)) % MOD;
}
ll get(int a, int b) {
	if (dp[a][b]) return dp[a][b];
	ll ret = 1;
	int limit = min(a, b);
	for (int i=1; i <= limit; i++) {
		ret += (((pascal(a, i) * pascal(b, i)) % MOD) * get_facto(i)) % MOD;
		ret %= MOD;
	}
	return dp[a][b] = ret;
}
int main() {
	int a, b, c;
	dp[1][1] = 2;
	cin >> a >> b >> c;
	ll ans = 1;
	ans *= get(a,b);
	ans %= MOD;
	ans *= get(b,c);
	ans %= MOD;
	ans *= get(c,a);
	ans %= MOD;
	cout << ans << endl;
}

D번 문제

http://codeforces.com/contest/869/problem/D

실제 대회당시 맞춘사람이 5명인가 밖에 안된다. 등록한사람이 7천명이 가까이되는데 말이다. 출제자가 D번문제와 E번 문제를 바꾸는게 나았을거라고 인정했다. 맞춘 사람 풀이를 보니, 실제로 가능한 경로를 모두 세되, 중복일 경우 최적화를 잘 적용한 것으로 보인다. 나중에 다시 도전해볼 예정이다.

E번 문제

http://codeforces.com/contest/869/problem/E

뭔가 풀 수 있을 것 같은데 못 풀 것 같은 문제이다. 2차원 세그먼트 트리나 쿼드 트리를 사용해야 한다고 한다. 세그먼트 트리와 쿼드 트리를 공부한 뒤 다시 도전할 예정이다.