Codeforces Round #663 (Div.2)

A. Suborrays

https://codeforces.com/contest/1391/problem/A

Problem - A - Codeforces

설명이 엄청나게 장황하게 써 있어서 약 15분 동안 문제를 쳐다만 보고 있었다.

그래서 종이에 써보면서 답을 알게 됐는데,

1 2 3 4 ... N을 출력해도 맞다는 것을 알게 되었다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		for (int i = 1; i <= N; i++)cout << i << ' ';
		cout << '\n';
	}
}

 

B. Fix You

https://codeforces.com/contest/1391/problem/B

Problem - B - Codeforces

 

UCPC 2020 본선 B번 문제와 비슷해서 문제 이해가 빨랐다. 다른 점은, 지도의 크기가 최대 100*100으로 아주 작다는 것이었고, 지도의 칸을 수정해서 모든 칸이 오른쪽 아래로 내려가도록 하는 것이라는 것이었다.

 

조건을 만족시키려면, 가장 마지막 줄은 무조건 RRRRRR....RRRC의 형태여야 하고,

나머지 줄은 마지막 칸만 D이면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int N, M, cnt = 0;
		char in;
		cin >> N >> M;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				cin >> in;
				if (i != N) {
					if (j == M && in == 'R')cnt++;
				}
				else {
					if (j != M && in == 'D')cnt++;
				}
			}
		}
		cout << cnt << '\n';
	}
}

 

C. Cyclic Permutations

https://codeforces.com/contest/1391/problem/C

Problem - C - Codeforces

 

순열의 길이 N을 입력받고, 일정한 조건에 따라 순열을 이용해 그래프를 만들 수 있다.

그래프 전체가 하나의 사이클인 경우의 수를 구하는 문제로, 입력 범위가 최대 100만인 것을 보고 수학 문제임을 직감했다.

손으로 N=3일 때, 답이 2가 나오는 것은 알아냈지만, 도무지 진전이 없었다.

N에 따라 모든 간선을 그려보면, 간선의 개수가 N-1개일 때 문제의 조건을 만족하지 않는다는 것을 알 수 있다.

전체 순열의 개수는 N!개, 간선의 개수가 N-1개가 되는 순열의 개수는 2^(N-1)개로, 답은 N! - 2^(N-1)개이다.

오버플로우에 유의하며 답을 출력하자.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	long long N, M;
	cin >> N;
	M = 1;
	long long cnt = 1, cnt2 = 1;
	while (M < N + 1) {
		cnt *= M;
		cnt %= 1000000007;
		M++;
	}
	M = 0;
	while (M < N - 1) {
		cnt2 *= 2;
		cnt2 %= 1000000007;
		M++;
	}
	cout << (cnt - cnt2 + 1000000007) % 1000000007 << '\n';
}