알고리즘/codeforces
Codeforces Round #751 (Div. 2)-C. Array Elimination
문제 설명 음이 아닌 정수로 이루어진 배열 $a_1, a_2, ..., a_n$ 이 주어진다. 정수 $k (1 \le k \le n) $ 에 대해서 제거라는 연산을 다음과 같이 정의하자. 서로 다른 배열의 인덱스 $(1 \le i_1 t; while(t--){ int n; cin >> n; int arr[n]; for(int i = 0; i > arr[i]; int cnt[31] = {}; for(int i = 0; i
알고리즘/codeforces
Codeforces Round #751 (Div. 2)-A. Two Subsequences
문제 설명 승현이에게 문자열 $s$가 주어진다. 우리는 다음 조건을 만족하는 비어있지 않은 두 문자열 $a$, $b$를 찾아야한다. 문자열 $a$와 $b$는 모두 $s$의 부분 문자열이다. 각 인덱스 $i$에 대해서 문자열 $s$의 문자 $s_i$는 반드시 문자열 $a$와 $b$ 둘중 하나에만 포함되어야 한다. 문자열 $a$는 가능한 사전적으로 작은 문자열이어야 한다. 그리고 $b$는 가능한 아무 문자열이라도 상관없다. 문자열 $s$가 주어졌을 때, 가능한 $a$와 $b$를 출력한다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 문자열 $s (2 \le |s| \le 100)$가 주어진다. 문자열 $..
알고리즘/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$ 보다 크거나 같기 때문이다. $(..
