Educational Codeforces Round 80 (Rated for Div. 2) 문제풀이

Educational Codeforces Round 80 (Rated for Div. 2)는 총 6문제였습니다.
A. Deadline
B. Yet another meme problem
C. Two arrays
D. Minmax problem
E. Messenger simulator
F. Red-Blue graph

저는 능력 부족으로 A,B,C 3문제 밖에 풀지 못했습니다... ㅠ
제가 푼 3문제에 대한 풀이를 작성해 보겠습니다.

A. Deadline

이번 대회 셋에서 가장 풀만한 문제였던 것 같습니다.
문제에서 N days 를 돌려야 돌아가는 프로그램을 x일을 투자하면 [N/(x+1)] (가우스) 로 줄어든다고 하였으므로,
 ' Adilbek be able to provide the generated results in no more than n$n$ days?'
라는 조건을 만족하기 위해서는 N >= x + [N/(x+1)] 이 만족하는지만 따져주면 됩니다.
x 는 1~N-1 까지만 봤습니다. ( x=N이면 조건을 만족할 수 없기 때문)

	#include <bits/stdc++.h>
	using namespace std;
	int T, N, d, temp, x;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	bool flag = false;
	temp = 987654321;
	x = 0;
	cin >> N >> d;
	if(N>=d){
	cout << "YES" << '\n';
	continue;
	}
	while(x+1<N){
	x++;
	if(d%(x+1)==0) temp = min(temp, x+(d/(x+1)));
	else temp = min(temp, x+(d/(x+1))+1);
	if(temp <= N){
	flag = true;
	break;
	}
	}
	if(flag) cout << "YES" << '\n';
	else cout << "NO" << '\n';
	}
	return 0;
	}

view raw A.deadline.cpp hosted with ❤ by GitHub

B. Yet another meme problem

풀이를 생각하기가 굉장히 까다로운 문제였습니다.

a*b+a+b = conc(a,b) 에서 (a+1)(b+1) = conc(a,b)+1 은 어렵지 않게 유도 가능합니다.

여기서 (a+1)(b+1) = conc(a,b)+1 이 식을 잘보고 생각을 했어야 합니다.
잘 생각해보면,  b = 9, 99, 999... 등 각 자리숫자가 모두 9 일 때,
LHS(좌항) : b+1 = 1000..... 의 꼴이므로 (a+1)*1000... 꼴이고,
RHS(우항) : conc(a,b)+1 은 LHS와 마찬가지로 (a+1)*1000.... 임을 알 수 있습니다.

예를 들면 아래와 같습니다.
a: 2, b: 99          일때 (a+1)(b+1) = (3)*100 = 299+1
a: 1432, b: 999    일때 (a+1)(b+1) = (1433)*1000 = 1432999+1

따라서 입력으로 A, B가 들어오면,
(1~A까지 A개 숫자) * (B보다 작거나 같은 각 자리가 9인 숫자의 개수) 가 답이됩니다.

이때 주의할 점이
(1) A,B 범위가 10^9 까지이므로 출력을 long long 형태로 해주어야하고
(2) B보다 작거나 같은 각 자리가 9인 숫자의 개수를 셀 때 정말 주의를 해야된다는 점입니다.

저는 (1),(2) 유형의 실수를 모두 했습니다.. ㅎㅎ
(2)번은 예를들어 B = 998 로 주어지면 이를 만족하는 개수는 9, 99 2개라는 점입니다.
(참고로 저는 while문 돌리면서 B 자리수 세주고, B/=10 이런식으로 진행하면서 B의 첫째자리가 9보다 크면 +1 해주었는데 그러면 998을 만족하는 개수가 3개 나왔었습니다....)
코드는 굉장히 간단합니다.

	#include <bits/stdc++.h>
	using namespace std;
	long long T, n, m, cnt;
	long long ans;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	cnt = 0;
	ans = 0;
	bool Minus = false;
	cin >> n >> m;
	while(1){
	if(m==9 && Minus) break;
	if(m<9) break;
	if(m%10<9) Minus=true;
	cnt++;
	m/=10;
	}
	ans = n*cnt;
	cout << ans << '\n';
	}
	return 0;
	}

view raw B. Yet another meme problem.cpp hosted with ❤ by GitHub

C. Two arrays

구현이 생각보다 어려운 문제였습니다.

문제를 정리해 생각해보면, 1~n 중 m개씩 m개씩 2번 뽑아서 array a에는 비감소(증가거나 같거나) 행렬이 되게, B에는 비증가(감소거나 같거나) 행렬이 되게 만들면 됩니다.
이때 a의 가장큰게 b의 가장작은거보다 작습니다.

잘 생각해보면 1~n개중 2*m개를 뽑아만 두면 저절로 배치 될 거라는걸 알 수 있습니다.
따라서 nH2*m 인 중복조합 문제임을 알 수 있습니다.
nH2*m = (n+2*m-1)C2*m 이므로 구하고자 하는 답은 (n+2*m-1)! / ((2*m)!(n-1)!) 입니다.

여기까지는 그럭저럭 생각만 하면 됩니다만, 이 중복 조합을 long long으로 구현하는 것이 저는 많이 까다로웠습니다.

저는 우선 factorial 을 구현하는 코드에서 착안하여 (어차피 (n+2*m-1)! 을 (n-1)! 으로 나누어 줄 것이므로) n*(n+1)*(n+2)*....*(n+2*m-1) 을 동작하는 함수를 만들었습니다.
( 이렇게 구한 값에 (2*m)! 만 나누어 주면 될 줄 알았는데..... 어디서 에러가 나는건진 모르겠지만 계속 답이 나오지 않아서... )
위의 곱셈을 진행하는 과정에서 (어차피 후에 (2*m)! 을 나누어 줄 것이기 때문에) 1~2*m 중에서 위 곱셈 과정의 중간값을 나눌 수 있으면 나누어주었습니다.

long long 으로 중복조합을 구현하는 과정이 좀 어려운 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MOD = 1000000000+7;
	int n, m, idx;
	long long ans, last;
	bool visited[20];
	long long H(int N, int a){
	long long res;
	if (N == 1)
	return N;
	else{
	res = N;
	for (int i = N - 1; i > a; i--){
	res *= i;
	for (int i = 2; i <= 2*m; ++i){
	if(visited[i]) continue;
	if(res%i==0){
	res/=i;
	visited[i] = true;
	}
	}
	if(res>MOD) res%=MOD;
	}
	return res%MOD;
	}
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> n >> m;
	ans = H(n+2*m-1, n-1);
	cout << ans << '\n';
	return 0;
	}

view raw C. Two arrays.cpp hosted with ❤ by GitHub