알고리즘/atcoder
AtCoder Beginner Contest 201 - A부터 C까지 업솔빙
Mynavi Programming Contest 2021（AtCoder Beginner Contest 201） A부터 C까지 업솔빙 두번째로 풀어본 Atcoder 문제셋이다. A번 문제는 그냥 풀었지만 B번에서 push_back()을 안하고 정렬을 하다가 계속 에러나서 순간 머리가 지진나서 시간을 좀 끌었다. 그리고 C번 문제는 딱 코드포스 1100점짜리 문제인거 같은데, 1시간동안 못풀었지만 완전탐색에 있는 유형을 하나 일깨워줬다. 이번 대회를 참여하면서 배운 것은 완전탐색을 항상 생각해 보는 자세 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Tiny Arithmetic Sequence (*12) 접기/펼치기 문제 설명 3개의 정수..
알고리즘/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$ 보다 크거나 같기 때문이다. $(..
알고리즘/codeforces
Codeforces Round #742 (Div. 2)-C. Carrying Conundrum
문제 설명 엘리스는 덧셈을 막 배우는 중이다. 엘리스는 덧셈에서 '올림'이라는 개념을 완전히 이해하지 못해서 원래라면 한 자릿수에서 덧셈의 결과가 10이 넘어가면 다음 한자릿수 왼쪽으로 넘어가야하지만 엘리스는 두자릿수 왼쪽으로 넘어가는 덧셈 연산을 했다. 예를 들어 일반적으로 $2039 + 2976$ 을 계산하면 $5015$ 이지만 엘리스는 $15005$ 가 나온다. 자세히 설명하자면 엘리스는 다음과 같은 과정으로 덧셈을 한다. $9$ 와 $6$ 을 더해서 $15$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($0,9$ 라고 써있는 열) $3$ 와 $7$ 을 더해서 $10$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($2,2$ ..
알고리즘/codeforces
Codeforces Round #742 (Div. 2)-B. MEXor Mixup
문제 설명 엘리스는 밥에게 두 정수 $a$와 $b (a > 0, b \le 0)$ 를 제시했다. 호기심 많은 소년인 밥은 모든 음이 아닌 정수를 원소로 가지는 배열의 모든 원소의 $MEX$ 값이 $a$이고, 배열의 모든 원소의 $XOR$ 값이 $b$를 만족하는 배열을 만들었다. 밥이 적은 가능한 최소길이를 가진 배열은 무엇일까? 배열의 $MEX$(Minimum EXcluded)는 배열의 원소가 아닌 값 중에서 가장 작은 음이 아닌 정수를 말하고, 배열의 $XOR$은 배열의 모든 원소를 XOR 비트 연산을 한 값을 말한다. Input 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 5 \cdot 10^4)$ 각 테스트케이스는 각각 배열의 $MEX$ 값과 $XOR$ 값을 나타..
