알고리즘/codeforces
Codeforces Round #745 (Div. 2)-C. Portal
문제 설명 이브는 $n \times m$ 크기를 가진 직사각형 $A$를 발견했다. 이 직사각형은 $n$ 개 행과 $m$ 개 열의 블록으로 이루어져 있다. 직사각형을 이루는 각 블록은 흑요석블록이거나 비어있다. 이브는 한번에 빈 블록을 흑요석 블록으로 바꾸거나, 흑요석 블록을 빈 블록으로 바꿀 수 있다. 크기 $a \times b$ 인 직사각형 $M$은 다음 조건을 모두 만족하면 포탈이다. $a \ge 5, b \ge 4$ 모든 $x(1 < x < a)$에 대해서 블록 $M_{x, 1}$ 과 $M_{x, b}$는 흑요석 블록이다. 모든 $x(1 < x < b)$에 대해서 블록 $M_{1, x}$ 과 $M_{a, x}$는 흑요석 블록이다. 모든 $x(1 < x < a), y(1 < y < b)$에 대해서 블..
알고리즘/codeforces
Codeforces Round #745 (Div. 2)-B. Diameter of Graph
문제 설명 성훈은 정점의 수가 $n$이고, 간선의 수가 $m$이며 그래프의 지름이 $k - 1$보다 작은 무방향 연결 그래프를 그리고 싶다. 또한 그 그래프는 self-loop와 다중 간선이 없어야 한다. (즉 각 간선은 서로 다른 두 정점과 연결되어야 하며, 두 정점사이에는 반드시 한개의 간선이 있어야 한다.) 그래프의 지름은 두 노드를 무작위로 선택할 때, 그 노드 사이에서 가질 수 있는 최대 거리를 의미한다. 두 노드 사이의 거리는 두 노드를 양 끝점으로 했을 때 두 노드 사이에 연결된 최소 간선의 개수를 말한다. 성훈은 이러한 그래프를 그릴 수 있는지 없는지 알고 싶다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$이 주어진다. 각 테스트 케이스에는 세 정수..
알고리즘/codeforces
Codeforces Round #745 (Div. 2)-A. CQXYM Count Permutations
문제 설명 효수는 길이가 $2n$ 인 순열중에서 특정 순열을 세고 있다. 순열은 $1$ 부터 $n$까지 $n$개의 수를 무작위로 나열한 것을 말한다. 예를들어 $[2, 3, 1, 5, 4]$ 는 순열이다. 하지만 $[1, 2, 2]$ 는 $2$ 가 배열에 2번 나타났기 때문에 순열이 아니다. 그리고 $[1, 3, 4]$ 는 배열의 길이가 $3$ 이지만 $4$ 가 포함되어 있기 때문이다. 길이가 $2n$ 인 순열 $p$는 $p_i < p_{i + 1}$ 를 만족하는 $i$의 개수가 $n$보다 크거나 같을 때 셀수 있다. 예를 들어 순열 $[1, 2, 3, 4]$ 는 셀수 있다. 왜냐하면 $p_i < p_{i + 1}$를 만족하는 $i$의 수가 3개고 이 수는 $n = 2$ 보다 크거나 같기 때문이다. $(..
