알고리즘/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$가 주어..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-B. Special Numbers
문제 설명 지우는 양의 정수로 이루어진 수열을 매우 좋아한다. 따라서 지우의 선생님인 혜린은 지우에게 오직 특별한 숫자로만 이루어진 수열에 관한 문제를 냈다. 서로 다른 음이 아닌 $n$의 제곱수의 합으로 양의 정수를 나타낼 수 있으면 그 수를 특별하다고 한다. 예를 들어 $n = 4$ 일때 $17$은 특별하다. 왜냐하면 $4^0 + 4^2 = 1 + 16 = 17$ 로 표현 할 수 있기 때문이다. 하지만 $9$ 는 그렇지 않다. 지우는 특별한 수가 오름차순으로 정렬되어있는 수열 중에서 $k$번째 수를 구해야한다. 이 숫자는 매우 크기 때문에 값을 $10^9 + 7$ 로 나눈 나머지값을 구한다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트..
알고리즘/codeforces
Codeforces Round #747 (Div. 2)-A. Consecutive Sum Riddle
문제 설명 지우는 정수에게 수수께끼를 냈다. 정수 $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$을 출력한다. 답이 여러개 있으면 아무거..
