알고리즘/codeforces
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)$ 각 테스트케이스의 두번째 줄에는 'L', 'R', 'U', 'D' 로만 이루어져 있는 $..
알고리즘/codeforces
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$이 할 작업이 남아있면 한개의 작업을 다른 사람에게 넘깁니다. 작업이 남아있지 않으면 생략합니다...
알고리즘/codeforces
Educational Codeforces Round 113 (Rated for Div. 2)-B. Chess Tournament
문제 설명 $n$명의 체스 선수가 참여할 체스 토너먼트가 곧 시작합니다! 모든 참가자는 다른 모든 참가자와 한번씩 게임을 진행해야 합니다. 한 경기가 끝나면 한 사람이 이기고, 다른 사람이 지는 경우와 두 참가자 모두 비기는 경우가 생깁니다. 각 참가자는 자신만의 성향을 가지고 있는데, 그 성향은 다음 중 하나입니다. 자신이 참여한 모든 게임에 지기 싫어하는 사람(즉 한번이라도 지지 않고 토너먼트를 종료해야함.) 최소 1번의 경기에 승리하고 싶어하는 사람 우리가 할 일은 모든 참가자의 성향을 만족하는 토너먼트 결과표가 존재하는지 아닌지 결정을 하는 것입니다. 만약 다양한 결과표가 존재하면 그것중 하나를 출력한다. 만약 존재하지 않는다면 불가능하다고 말해야 합니다. Input 첫번째 줄에는 테스트 케이스의..
알고리즘/codeforces
Educational Codeforces Round 113 (Rated for Div. 2)-A. Balanced Substring
문제 설명 알파벳 'a'와 'b'로 이루어지고 $n$개의 문자로 이루어진 문자열 $s$가 주어진다. 이 문자열의 index는 $1$ 번부터 $n$번까지로 나타낸다. $s[l;r]$은 index $l$ 부터 $r$까지 string $s$의 부분 문자열이다. 이때 index $r$과 $s$모두 포함한다. 어떤 문자열이 문자 'a'의 개수와 문자 'b'의 개수가 같으면 그 문자열은 "균형잡혔다"고 말한다. 예를들어 문자열 "baba"와 "aabbab"는 균형잡혔지만 문자열 "aaab"와 "b"는 균형잡히지 않았다. 한 문자열에서 균형잡힌 부분 문자열 $s[l:r]$ 을 찾는 것이 우리의 목표이다. 균형잡힌 문자열을 찾은 경우 $l$과 $r(1 \le l..
알고리즘/codeforces
Educational Codeforces Round 115 (Rated for Div. 2)-C. Delete Two Elements
문제 설명 모노폴리는 정수 $n$개로 이루어진 배열 $a$를 가지고 있다. $a$의 산술평균을 $k$라고 가정하자.($k$는 정수가 아닐 수 있다.) 모노폴리는 정확히 배열 $a$에 있는 숫자 2개를 지워서 정확히 $n - 2$개의 숫자들로 이루어진 평균을 여전히 $k$로 유지하고 싶다. 우리가 해야할 것은 만약 두 숫자를 지워도 여전히 평균이 $k$가 되는 숫자들의 인덱스 쌍 $[i, j](i < j)$ 의 개수를 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 배열에 있는 원소의 수 $n (3 \le n \le 2 \cdot 10^5)$ 이 주어진다. 각 테스트케이스의 두번째 줄에는 ..
알고리즘/codeforces
Educational Codeforces Round 115 (Rated for Div. 2)-B. Groups
문제 설명 $n$명의 학생들은 프로그래밍 수업의 첫 수업을 참여했다 ($n$은 짝수이다). 모든 학생들은 반드시 두 그룹으로 나뉘어야 한다. 각 그룹에 속한 학생은 반드시 주중에 있는 요일(월요일, 화요일, 수요일, 목요일, 금요일) 중 한 요일에 참가할 수 있어야 한다. 그리고 각 그룹이 선택한 요일은 반드시 서로 달라야 한다. 마지막으로 각 그룹에 속해있는 학생들의 숫자는 서로 같아야 한다. 각 학생들은 어느 요일에 수업을 참여할 수 있는지, 없는지를 적게하는 설문지를 채워서 제출했다. 우리가 해야할 것은 두 그룹의 시간 계획을 세우기 위해서 주중에 있는 서로 다른 요일을 선택할 수 있는지 없는지 결정하는 것이다. (첫번째 그룹은 첫번째 선택한 요일에 반드시 수업을 참여해야 하고, 두번째 그룹은 두번..
