알고리즘/codeforces
Codeforces Round #734 (Div. 3)-C. Interesting Story
문제 설명 커리는 소설을 쓰고 싶다. 커리는 진짜 이상한 작가인데 오직 문자 'a', 'b', 'c', 'd', 'e'만 사용한다. 이야기를 구성하기 위해서 커리는 주어진 소문자만으로 이루어진 단어 $n$개를 작성했다. 커리는 재밌는 이야기를 만들기 위해서 선택해야 하는 최대 단어수를 구해야 한다. 단어를 선택하는 순서는 중요하지 않다. 이야기를 구성하는 모든 단어에 있는 5개의 문자중 한 문자의 개수가 다른 4개의 모든 문자의 개수 총합보다 큰 경우가 있으면 이 이야기는 흥미로운 이야기라고 한다. 예를 들어 이야기가 3단어 "bac", "aaada", "e"로 이루어져 있다면 이 이야기는 흥미로운 이야기이다. 왜냐하면 단어 '..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-B2. Wonderful Coloring - 2
문제 설명 폴은 정수 $a_1, a_2, ..., a_n$ 으로 이루어진 수열을 생각했다. 폴은 이 정수들을 $k$개 색깔의 분필로 칠하고 싶다. 다음의 조건을 만족하면서 색칠을 하면 환상적인 수열이라고 말한다. 수열의 각 원소는 $k$개의 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 원소는 서로 다른 값을 가져야한다. 각 $k$번째 색깔로 칠한 원소의 개수는 모두 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 원소의 개수가 최대가 되어야 한다. 예를 들어 수열 $a = [3, 1, 1, 1, 10, 3, 10, 10, 2]$ 이고 $k = 3$ 인 경우 수열의 환상적인 색칠의 한가지 경우는 다음과 같다. 폴이 주어진 수열 $a$를 환상적인 색칠을 할 수 있..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-B1. Wonderful Coloring - 1
문제 설명 메리는 알파벳 소문자로만 이루어진 문자열을 좋아한다. 메리는 이 문자열에 속해있는 문자 하나 하나를 빨간색 분필 혹은 초록색 분필로 색칠하려고 한다. 안그러면 색칠을 안해도 좋다. 우리는 다음 조건을 만족하는 방식으로 문자열을 색칠하면 최고로 좋은 색칠이라고 말한다. 문자열의 각 문자는 빨간색, 초록색 색깔중 하나만 색칠하거나 색칠하지 않아야 한다. 같은 색깔로 색칠한 모든 두 문자는 서로 다른 문자여야 한다. 빨간색으로 색칠한 문자와 초록색으로 색칠한 문자의 개수는 같아야 한다. 위에서 언급한 3개의 조건을 만족하면서 색칠한 문자의 개수가 최대가 되어야 한다. 예를 들어 문자열 $s = kzaaa$인 경우 최고로 좋은 색칠의 한가지 경우는 다음과 같다. 우리는 최고로 환상적인 색칠인 경우에서..
알고리즘/codeforces
Codeforces Round #734 (Div. 3)-A. Polycarp and Coins
문제 설명 동하는 $n$원을 지불해야한다. 동하는 2가지 동전밖에 가지고 있지 않은데, $1$원짜리 동전과 $2$원짜리 동전이다. 동하는 이 동전을 최대한 비슷하게 지불하고 싶어한다. 따라서 동하는 1원짜리 동전과 2원짜리 동전사이의 개수를 최소화 하는 방향으로 돈을 지불하고 싶다. 1원짜리 동전의 개수를 $c_1$, 2원짜리 동전의 개수를 $c_2$라고 할때, 전체 값은 정확히 $n$원이 되어야 한다. 즉 $(c_1 + 2 \cdot c_2 = n)$ 이 식을 만족해야 한다. 그리고 $c_1$과 $c_2$ 차이의 절대값이 최대한 작게 만들어야 한다. 즉 우리는 반드시 이 식의 값을 최소화 해야 한다. $(|c_1 - c_2|)$ Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le ..
알고리즘/codeforces
Codeforces Round #735 (Div. 2)-C. Mikasa
문제 설명 두 정수 $n$과 $m$이 주어진다. 수열 $n \oplus 0, n \oplus 1, ..., n \oplus m$의 $MEX$값을 구하시오. 음이 아닌 정수를 원소로 가진 수열의 $MEX$는 이 수열에 나타나지 않은 음이 아닌 정수중 가장 작은 값을 말한다. 예를 들어서 $MEX(0, 1, 2, 4) = 3$ 이다. 그리고 $MEX(1, 2021) = 0$ 이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 30000)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 두 정수 $n, m (0 \le n, m \le 10^9)$ 이 주어진다. Output 각 테스트케이스마다 문제의 답을 출력한다. Example input 5 3 5 4 6 3 2 69 696 1..
알고리즘/codeforces
Codeforces Round #735 (Div. 2)-B. Cobb
문제 설명 정수 $n$개 $a_1, a_2,..., a_n$ 와 정수 $k$가 주어졌을 때 $1 \le i < j \le n$ 를 만족하는 정수 쌍 $(i, j)$에 대해서 $i \cdot j - k \cdot (a_i|a_j)$ 의 최대값을 구하라. $|$이 기호는 비트 OR연산자이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10000)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 두 정수 $n (2 \le n \le 10^5)$와 $k (1 \le k \le min(n, 100))$이 주어진다. 각 테스트 케이스의 두번째 줄에는 $n$개의 정수 $a_1, a_2, ..., a_n (0 \le a_i \le n)$ 가 주어진다. Output 각 테스트케이스마다 주..
