To the Expert

문제 설명 알파벳 '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..

문제 설명 모노폴리는 정수 $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)$ 이 주어진다. 각 테스트케이스의 두번째 줄에는 ..

문제 설명 $n$명의 학생들은 프로그래밍 수업의 첫 수업을 참여했다 ($n$은 짝수이다). 모든 학생들은 반드시 두 그룹으로 나뉘어야 한다. 각 그룹에 속한 학생은 반드시 주중에 있는 요일(월요일, 화요일, 수요일, 목요일, 금요일) 중 한 요일에 참가할 수 있어야 한다. 그리고 각 그룹이 선택한 요일은 반드시 서로 달라야 한다. 마지막으로 각 그룹에 속해있는 학생들의 숫자는 서로 같아야 한다. 각 학생들은 어느 요일에 수업을 참여할 수 있는지, 없는지를 적게하는 설문지를 채워서 제출했다. 우리가 해야할 것은 두 그룹의 시간 계획을 세우기 위해서 주중에 있는 서로 다른 요일을 선택할 수 있는지 없는지 결정하는 것이다. (첫번째 그룹은 첫번째 선택한 요일에 반드시 수업을 참여해야 하고, 두번째 그룹은 두번..

문제 설명 모노폴리는 컴퓨터게임을 하는 중이다. 모노폴리는 이 게임의 첫번째 단계를 클리어하고 싶다. 첫번째 단계는 $2$개의 행과 $n$개의 열의 격자판으로 이루어져 있는 직사각형이 주어진다. 모노폴리는 $(1, 1)$ 칸에서 출발하는 캐릭터를 조작한다. 모노폴리의 캐릭터는 인접하는 격자나 인접하는 대각선 한칸으로 이동할 수 있다. 즉 엄밀하게 말하자면 캐릭터는 한번에 $(x_1, y_1)$ 에서 $(x_2, y_2)$ 까지 $|x_1 - x_2| \le 1, |y_1 - y_2| \le 1$을 만족하면 이동할 수 있다. 또한 격자 바깥으로는 캐릭터가 움직일 수 없다. 몇개의 칸에는 함정이 있다. 만약 모노폴리의 캐릭터가 함정을 밟으면 캐릭터가 죽고, 게임이 끝난다. 이 게임을 클리어하기 위해서는 모노..

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 알고리즘, 정수론 문제가 초반부에 나오는 것 같다. 이번 대회를 참여하면서 배운 것은 나머..

문제 설명 지우는 지금 너무 배고프다. 그래서 가장 좋아하는 음식을 먹고 싶은데 일단 이 과제만 풀고 먹으려고 다짐한다. 지우가 밥을 먹을 수 있게 이 문제를 푸는 것을 도와줄 수 있을까? 자료구조에는 $2^k - 1$개 노드을 가지는 완전 이진트리를 알고 있다. 완전 이진트리는 $1$ 부터 $2^{k - 1} - 1$개 노드를 가지고 있고, 부모노드가 $i$일때 반드시 2개의 자식 노드$2i, 2i + 1$를 가지는 이진트리를 말한다. 그리고 $2{k-1}$부터 $2^k - 1$까지 번호를 가지고 있는 노드는 이 노드에서 나오는 간선이 없다는 것도 완전 이진트리의 특징이다. 우리는 이 완전 이진트리의 노드를 큐브의 6가지 색깔로 칠하고 싶다. 모든 연결된 노드가 반드시 큐브의 이웃한 색깔로 칠해지는 경..

문제 설명 지우에게 문자 $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$가 주어..

문제 설명 지우는 양의 정수로 이루어진 수열을 매우 좋아한다. 따라서 지우의 선생님인 혜린은 지우에게 오직 특별한 숫자로만 이루어진 수열에 관한 문제를 냈다. 서로 다른 음이 아닌 $n$의 제곱수의 합으로 양의 정수를 나타낼 수 있으면 그 수를 특별하다고 한다. 예를 들어 $n = 4$ 일때 $17$은 특별하다. 왜냐하면 $4^0 + 4^2 = 1 + 16 = 17$ 로 표현 할 수 있기 때문이다. 하지만 $9$ 는 그렇지 않다. 지우는 특별한 수가 오름차순으로 정렬되어있는 수열 중에서 $k$번째 수를 구해야한다. 이 숫자는 매우 크기 때문에 값을 $10^9 + 7$ 로 나눈 나머지값을 구한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트..

문제 설명 지우는 정수에게 수수께끼를 냈다. 정수 $n$이 있는데, 우리가 구해야 할 것은 $-10^{18} \le l < r \le 10^{18}$ 과 $l + (l + 1) + ... + (r - l) + r = n$ 을 만족하는 두 정수 $l$과 $r$을 구해야 한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $n (1 \le n \le 10^{18})$이 주어진다. Output 각 테스트케이스마다 $-10^{18} \le l < r \le 10^{18}$ 과 $l + (l + 1) + ... + (r - l) + r = n$ 을 만족하는 두 정수 $l$과 $r$을 출력한다. 답이 여러개 있으면 아무거..

문제 설명 핫산에게 정수 $n$개로 이루어진 배열이 주어진다. 핫산은 그의 친구 나비한테 이 배열을 오름차순으로 만들어야 한다고 말했다. 하지만 이 뿐이라면 문제가 너무 쉬워지기 때문에 정렬을 할 때 오직 다음 연산만을 사용해야 한다는 제약을 추가했다. $1 \le i,j \le n$, $|i - j| \ge x$ 를 만족하는 index $i$와 $j$를 선택하고, 그 다음 $a_i$와 $a_j$의 위치를 바꾼다. 우리가 해야할 것은 나비가 위에서 주어진 연산을 사용해서 배열을 오름차순으로 만들 수 있는지 판별하는 것이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 두 정수 $n$과 $x (2 \le n \le x..