알고리즘/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$은 짝수이다). 모든 학생들은 반드시 두 그룹으로 나뉘어야 한다. 각 그룹에 속한 학생은 반드시 주중에 있는 요일(월요일, 화요일, 수요일, 목요일, 금요일) 중 한 요일에 참가할 수 있어야 한다. 그리고 각 그룹이 선택한 요일은 반드시 서로 달라야 한다. 마지막으로 각 그룹에 속해있는 학생들의 숫자는 서로 같아야 한다. 각 학생들은 어느 요일에 수업을 참여할 수 있는지, 없는지를 적게하는 설문지를 채워서 제출했다. 우리가 해야할 것은 두 그룹의 시간 계획을 세우기 위해서 주중에 있는 서로 다른 요일을 선택할 수 있는지 없는지 결정하는 것이다. (첫번째 그룹은 첫번째 선택한 요일에 반드시 수업을 참여해야 하고, 두번째 그룹은 두번..
알고리즘/codeforces
Educational Codeforces Round 115 (Rated for Div. 2)-A. Computer Game
문제 설명 모노폴리는 컴퓨터게임을 하는 중이다. 모노폴리는 이 게임의 첫번째 단계를 클리어하고 싶다. 첫번째 단계는 $2$개의 행과 $n$개의 열의 격자판으로 이루어져 있는 직사각형이 주어진다. 모노폴리는 $(1, 1)$ 칸에서 출발하는 캐릭터를 조작한다. 모노폴리의 캐릭터는 인접하는 격자나 인접하는 대각선 한칸으로 이동할 수 있다. 즉 엄밀하게 말하자면 캐릭터는 한번에 $(x_1, y_1)$ 에서 $(x_2, y_2)$ 까지 $|x_1 - x_2| \le 1, |y_1 - y_2| \le 1$을 만족하면 이동할 수 있다. 또한 격자 바깥으로는 캐릭터가 움직일 수 없다. 몇개의 칸에는 함정이 있다. 만약 모노폴리의 캐릭터가 함정을 밟으면 캐릭터가 죽고, 게임이 끝난다. 이 게임을 클리어하기 위해서는 모노..
알고리즘/atcoder
AtCoder Beginner Contest 200 - A부터 C까지 업솔빙
KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200） A부터 C까지 업솔빙 https://codeforces.com/blog/entry/66909 3년전 글이지만 이 글을 읽고 코드포스 레이팅을 올리려면 Atcoder에 있는 문제도 푸는 것을 추천하길래 오늘부터 Atcoder에 있는 A부터 C(D)번까지 문제를 직접 풀어보고 해설까지 해볼 것이다. C번 문제혹은 D번문제까지 해설하는 기준은 내가 대회 시간에 풀려고 시도했던 문제까지 업솔빙 하고 해설을 하려고 한다. 처음으로 풀어본 Atcoder 문제는 생각보다 쉬운듯 하면서 내가 모르는 well-known 알고리즘, 정수론 문제가 초반부에 나오는 것 같다. 이번 대회를 참여하면서 배운 것은 나머..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-E1. Rubik's Cube Coloring (easy version)
문제 설명 지우는 지금 너무 배고프다. 그래서 가장 좋아하는 음식을 먹고 싶은데 일단 이 과제만 풀고 먹으려고 다짐한다. 지우가 밥을 먹을 수 있게 이 문제를 푸는 것을 도와줄 수 있을까? 자료구조에는 $2^k - 1$개 노드을 가지는 완전 이진트리를 알고 있다. 완전 이진트리는 $1$ 부터 $2^{k - 1} - 1$개 노드를 가지고 있고, 부모노드가 $i$일때 반드시 2개의 자식 노드$2i, 2i + 1$를 가지는 이진트리를 말한다. 그리고 $2{k-1}$부터 $2^k - 1$까지 번호를 가지고 있는 노드는 이 노드에서 나오는 간선이 없다는 것도 완전 이진트리의 특징이다. 우리는 이 완전 이진트리의 노드를 큐브의 6가지 색깔로 칠하고 싶다. 모든 연결된 노드가 반드시 큐브의 이웃한 색깔로 칠해지는 경..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-C. Make Them Equal
문제 설명 지우에게 문자 $s_1, s_2, ..., s_n$로 이루어진 문자열 $s$ 와 문자 $c$가 주어진다. 지우는 문자열에 있는 모든 문자를 최소 연산을 사용해서 $c$로 만들고 싶다. 우리가 사용해야할 연산은 다음과 같다. 지우는 $(1 \le x \le n)$을 만족하는 숫자 $x$를 선택하고, $x$로 나누어 떨어지지 않는 모든 $i$에 대해서 $s_i$를 $c$로 바꾼다. 우리는 한 문자열에 있는 모든 문자를 $c$로 만들어야 하는 연산의 최소 개수를 구해야 한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $n$과 $(3 \le n \le 3\cdot 10^5)$ 소문자 알파벳 $c$가 주어..
