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이면 조건을 만족할 수 없기 때문)

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개 나왔었습니다....)
코드는 굉장히 간단합니다.

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 으로 중복조합을 구현하는 과정이 좀 어려운 문제였습니다.