Educational Codeforces Round 115 (Rated for Div. 2) (virtual)

21.10.21

B번에서 정말 바보같이 문제 제대로 안읽고 풀어서 틀리고 C번 고쳤을때 자료형을 생각안한게 참 아쉽다...

A

Problem - A - Codeforces

간단한 bfs 문제 였다.

그냥 시작점에서 끝점으로 갈 수 있는지 묻는 문제로 다른 훨씬 간단한 쉬운 풀이법도 많을테지만 그냥 가장 먼저 생각난게 bfs라 걍 이걸로 풀음

B

Problem - B - Codeforces

두개의 그룹으로 사람들을 나누는데 똑같은 수의 사람들이 그룹에 있어야 하고 모든 사람이 둘중 하나의 그룹에는 들어가야 하며 두개의 그룹이 선택한 요일이 다를 수 있는지를 묻는 문제였다.

그냥 naive하게 완탐 조지면 된다.

C

Problem - C - Codeforces

배열 중 2개의 element들을 제거해 제거 전 배열의 평균과 똑같은 배열을 만들 수 있는 pair의 개수가 몇개인지 묻는 문제였다.

처음에 이분탐색으로 찾고 naive하게 한칸 한칸 가며 세는 식으로 했는데 TLE가 떠서 map으로 바꾸어 이분 탐색을 했으나 바보같이 또 자료형 크기를 생각하지 않고 풀어서 오버 플로우가 나서 틀렸다.... ㅠㅠㅠ

D

Problem - D - Codeforces

문제라는 것이 1개씩 주어지는데, 문제별로 주제, 난이도가 정해져있다.

이 문제들 중 3개를 고르는데 다음 조건중 적어도 1개를 만족하게 고르는 개수를 구하는 문제다.

1. 세 문제의 난이도가 전부 다르다.
2. 세 문제의 주제가 전부 다르다.

전체 고르는 경우의 수 - 세 문제가 전부 같은 난이도 같은 주제 - 두 문제가 같은 난이도 같은 주제이며 나머지 문제는 난이도나 주제가 다른 경우 - 한 문제가 a,b인 경우 나머지 두 문제가 a,x y,b일때 x가 b가 아니고 y가 a가 아닌 경우의 수

를 구해주면 된다.

먼저 map으로 {주제, 난이도}로 개수를 세고, 두개의 배열 a,b의 각각에 주제, 난이도 별로 갯수를 세준다.

전체 고르는 수는 조합으로 $_NC_3$ 때리면 된다.

세 문제가 전부 같은 난이도 같은 주제이기 위해선, map[{주제, 난이도}] = $n$이라 할때 $_nC_3$ 때리면 된다.

두 문제가 같은 난이도 같은 주제이며 나머지 문제는 난이도나 주제가 다른 경우는 $_nC_2 \times$(N - n)로 구할 수 있다.

마지막으로 한 문제가 a,b이며 나머지 두 문제가 a,x y,b (x ≠ b, y ≠a)인 경우는

n * ((a[주제] - n) * (b[난이도] - n))로 구할 수 있다.