반응형

전체 글 137

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 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 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 Round #745 (Div. 2)-B. Diameter of Graph

문제 설명 성훈은 정점의 수가 $n$이고, 간선의 수가 $m$이며 그래프의 지름이 $k - 1$보다 작은 무방향 연결 그래프를 그리고 싶다. 또한 그 그래프는 self-loop와 다중 간선이 없어야 한다. (즉 각 간선은 서로 다른 두 정점과 연결되어야 하며, 두 정점사이에는 반드시 한개의 간선이 있어야 한다.) 그래프의 지름은 두 노드를 무작위로 선택할 때, 그 노드 사이에서 가질 수 있는 최대 거리를 의미한다. 두 노드 사이의 거리는 두 노드를 양 끝점으로 했을 때 두 노드 사이에 연결된 최소 간선의 개수를 말한다. 성훈은 이러한 그래프를 그릴 수 있는지 없는지 알고 싶다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$이 주어진다. 각 테스트 케이스에는 세 정수..

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 Round #742 (Div. 2)-C. Carrying Conundrum

문제 설명 엘리스는 덧셈을 막 배우는 중이다. 엘리스는 덧셈에서 &#39;올림&#39;이라는 개념을 완전히 이해하지 못해서 원래라면 한 자릿수에서 덧셈의 결과가 10이 넘어가면 다음 한자릿수 왼쪽으로 넘어가야하지만 엘리스는 두자릿수 왼쪽으로 넘어가는 덧셈 연산을 했다. 예를 들어 일반적으로 $2039 + 2976$ 을 계산하면 $5015$ 이지만 엘리스는 $15005$ 가 나온다. 자세히 설명하자면 엘리스는 다음과 같은 과정으로 덧셈을 한다. $9$ 와 $6$ 을 더해서 $15$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($0,9$ 라고 써있는 열) $3$ 와 $7$ 을 더해서 $10$ 라는 결과를 도출한다. 그리고 $1$ 을 왼쪽으로 2열 이동해서 올린다. ($2,2$ ..

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$ 값을 나타..

Codeforces Round #742 (Div. 2)-A. Domino Disaster

문제 설명 엘리스는 $2 \times n$ 크기 타일을 가지고 있다. 엘리스는 타일을 $1 \times 2$ 크기 도미노로 완전히 덮고 싶다. 엘리스는 도미노를 수직, 수평으로 놓을 수 있고 도미노끼리 겹치면 안된다. 엘리스는 지금 밥에게 타일의 한 행을 보여준다. 우리는 엘리스가 보여준 타일의 한 행을 가지고 다른 행이 어떻게 구성됐는지 알아내야 한다. Input 첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 5000)$ 각 테스트케이스의 첫번째 줄에는 타일의 가로 길이 $n$이 주어진다. $(1 \le n \le 100)$ 각 테스트케이스의 두번째 줄에는 &#39;L&#39;, &#39;R&#39;, &#39;U&#39;, &#39;D&#39; 로만 이루어져 있는 $..

Educational Codeforces Round 113 (Rated for Div. 2)-C. Jury Meeting

문제 설명 다가오는 대회의 심사위원 회의를 하기위해 $n$명의 사람이 모였습니다. $i$번째 심사위원은 서류 $a_i$개를 처리해야하고, 서로 공유해서 처리하고 싶어합니다. 먼저 심사위원은 각자의 작업이 얼마나 남아있는지 설명하는 방식을 순서에 맞게 하자고 결정을 했습니다. $p$를 $1$부터 $n$까지 숫자로 이루어진 순열로 정합시다. ($1$부터 $n$까지 숫자가 한번씩 나오는 크기가 $n$인 배열이 $p$입니다.) 이후 토의는 다음과 같은 순서로 이루어집니다. 만약 심사위원 $p_1$이 할 작업이 남아있면 한개의 작업을 다른 사람에게 넘깁니다. 작업이 남아있지 않으면 생략합니다. 만약 심사위원 $p_2$이 할 작업이 남아있면 한개의 작업을 다른 사람에게 넘깁니다. 작업이 남아있지 않으면 생략합니다...

Educational Codeforces Round 113 (Rated for Div. 2)-B. Chess Tournament

문제 설명 $n$명의 체스 선수가 참여할 체스 토너먼트가 곧 시작합니다! 모든 참가자는 다른 모든 참가자와 한번씩 게임을 진행해야 합니다. 한 경기가 끝나면 한 사람이 이기고, 다른 사람이 지는 경우와 두 참가자 모두 비기는 경우가 생깁니다. 각 참가자는 자신만의 성향을 가지고 있는데, 그 성향은 다음 중 하나입니다. 자신이 참여한 모든 게임에 지기 싫어하는 사람(즉 한번이라도 지지 않고 토너먼트를 종료해야함.) 최소 1번의 경기에 승리하고 싶어하는 사람 우리가 할 일은 모든 참가자의 성향을 만족하는 토너먼트 결과표가 존재하는지 아닌지 결정을 하는 것입니다. 만약 다양한 결과표가 존재하면 그것중 하나를 출력한다. 만약 존재하지 않는다면 불가능하다고 말해야 합니다. Input 첫번째 줄에는 테스트 케이스의..

반응형