[CF] Round #678 (Div. 2) _ 201024

(2020년 10월 25일에 작성한 글입니다.)

 

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

 

A, B, C를 빨리 푼 덕분에 레이팅 엄청 올랐네...

당분간은 그린 갈 걱정 안 해도 되겠다...ㅜㅜ

​

A.

시그마가 있고 식이 복잡했는데

조금 적어보니까 모든 수의 합이 M이면 YES, 아니면 NO여서 금방 풀었다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N, M;
	int i;

	cin >> T;
	while (T--) {
		cin >> N >> M;
		int sum = 0;
		for (i = 0; i < N; i++) {
			int temp;
			cin >> temp;
			sum += temp;
		}
		if (sum == M) {
			cout << "YES" << '\n';
		}
		else {
			cout << "NO" << '\n';
		}
	}

	return 0;
}

​

B.

배열 안의 내용이 non-negative integer라고 했기 때문에 0도 가능했고,

지금 보니까 어떻게 이 생각을 했는지 좀 놀라운데

전부 다 0으로 채워놓고, X자로 1을 채웠다.

만약 N이 짝수라면 각 행, 열들의 합은 모두 2가 되는데

N이 홀수라면 가운데 행, 열은 합이 1이라서

arr[0][N/2] = arr[N/2][0] = 1

이런식으로 가운데에 1을 넣어줬다.

그리고 N이 1이면 그냥 arr[0][0] = 2니까 그것도 체크해줬고.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int N;
	int i, j;

	cin >> T;
	while (T--) {
		cin >> N;
		vector<vector<int>> arr(N, vector<int>(N, 0));
		for (i = 0; i < N; i++) {
			arr[i][i] = 1;
			arr[i][N - 1 - i] = 1;
		}
		if (N == 1) {
			arr[0][0] = 2;
		}
		else if (N % 2) {
			arr[0][N / 2] = 1;
			arr[N / 2][0] = 1;
		}

		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				cout << arr[i][j] << ' ';
			}
			cout << '\n';
		}
	}

	return 0;
}

​

C.

POS까지 가는 길을 체크해야되는데

왼쪽으로 이동할때는 X보다 큰 수가 있었다는 거고

오른쪽으로 이동할때는 X보다 작은 수가 있었다는거다.

이때 등호가 들어있기 때문에 작은 수들의 개수에서 1을 빼줘야 하고

그래서 답은 ((X - 1) P smaller) * ((N - X) P larger) * (N - 1 - smaller - larger)!

이다.

P는 permutation을 의미한다.

smaller은 X보다 작은 수 중 자리가 정해져 있는 수의 개수

larger은 X보다 큰 수 중 자리가 정해져 있는 수의 개수

나머지 수들은 모든 순열이 가능하니까 팩토리얼.

나머지 연산을 적절히 하면서 계산하는 게 포인트

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, X, POS;
	int left, right, mid;
	int smaller, larger;
	ll ans;
	int i;

	cin >> N >> X >> POS;
	smaller = larger = 0;
	left = 0;
	right = N;

	while (left < right) {
		mid = (left + right) / 2;
		if (mid <= POS) {
			if (mid != POS) {
				smaller++;
			}
			left = mid + 1;
		}
		else {
			larger++;
			right = mid;
		}
	}

	ans = 1;
	ll n;
	int cnt;
	for (n = (ll)(N - X), cnt = 0; cnt < larger; cnt++, n--) {
		ans *= n;
		ans %= MOD;
	}
	for (n = (ll)(X - 1), cnt = 0; cnt < smaller; cnt++, n--) {
		ans *= n;
		ans %= MOD;
	}
	for (n = 1; n <= (ll)(N - smaller - larger - 1); n++) {
		ans *= n;
		ans %= MOD;
	}

	cout << ans << '\n';

	return 0;
}