알고리즘/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 각 테스트케이스마다 주..
알고리즘/codeforces
Codeforces Round #735 (Div. 2)-A. Cherry
문제 설명 정수 $n$개 $a_1, a_2,..., a_n$ 이 주어졌을 때 $1 \le l < r \le n$ 를 만족하는 정수 쌍 $(l, r)$에 대해서 $max(a_l, a_{l + 1}, ..., a_r) \cdot min(a_l, a_{l + 1}, ..., a_r)$ 의 최대값을 출력하라. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10000)$ 이 주어진다. 각 테스트 케이스의 첫번째 줄에는 정수 $n (2 \le n \le 10^5)$ 가 주어진다. 각 테스트 케이스의 두번째 줄에는 $n$개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 10^6)$ 가 주어진다. Output 각 테스트케이스마다 주어진 수식의 최대값을 나타내는 정수를 ..
알고리즘/codeforces
Codeforces Round #738 (Div. 2)-D1. Mocha and Diana (Easy Version)
문제 설명 그래프이론에서 숲이란 사이클이 없는 무뱡향 그래프 이다. 이때 모든 노드와 연결될 필요 없다. 노원구에 사는 동환과 영준은 서로 친구이다. 이들은 모두 재벌이라서 각자 $1$부터 $n$까지 번호가 붙여있는 노드가 있는 숲을 가지고있다. 그리고 이들은 숲에 간선을 다음과 같은 방식으로 추가하는 것을 즐긴다. 간선을 추가하고 두 숲 모두 여전히 숲을 유지해야한다. 두 숲 모두 같은 간선을 추가해야 한다. 즉 간선 $(u, v)$를 동환이의 숲에 추가한다면 동일한 간선 $(u, v)$를 영준이에 숲에 추가해야하고 이 반대의 경우도 성립한다. 동환이와 영준이는 연결 할 수 있는 최대한 많은 간선을 연결하고 싶어한다. Input 첫번째 줄에는 각각 노드의 수, 동환이의 숲에 있는 초기 간선의 수, 영준..
