알고리즘/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 첫번째 줄에는 각각 노드의 수, 동환이의 숲에 있는 초기 간선의 수, 영준..
알고리즘/codeforces
Codeforces Round #738 (Div. 2)-C. Mocha and Hiking
문제 설명 노원구에는 마을 $n + 1$개와 방향이 있는 도로 $2n - 1$개가 있다. 노원구에 있는 도로는 다음 두 종류가 있다. 도로 $n - 1$ 개는 $1 \le i \le n - 1$을 만족하는 모든 $i$에 대해서 마을 $i$에서 마을 $i + 1$로 연결되어 있다. 도로 $n$개는 수열 $a_1, ..., a_n$ 으로 제시된다. $1 \le i \le n$을 만족하는 모든 $i$에 대해서 만약 $a_i = 0$이면 이 도로는 마을 $i$에서 마을 $n + 1$으로 연결한다. $a_i = 1$이면 마을 $n + 1$에서 마을 $i$로 연결한다. 동환이는 이번주에 노원구를 택시로 돌아볼 생각이다. 지루한 여행이 되지 않기 위해 모든 마을을 정확히 한번만 방문하려고 한다. 동환이는 아무 마을에..
알고리즘/codeforces
Codeforces Round #738 (Div. 2)-B. Mocha and Red and Blue
문제 설명 타일 $n$개가 일렬로 나란히 놓여있다. 그리고 이 타일은 빨간색 혹은 파란색으로 색칠할 수 있다. 이 타일중 몇개는 이미 색칠되어 있을 수도 있다. 그렇지 않은 타일은 빈칸으로 놓여있다. 우리가 해야할 일은 빈 타일을 무슨색으로 칠해야 할지 결정해야 하는것이다. 몇개의 인접한 타일 쌍은 같은 색으로 칠해져 있을 수 있고 불완전하다. 우리는 같은 색으로 칠해져 있는 인접한 두 타일의 쌍의 개수를 불완전성 이라고 한다. 예를 들어 "BRRRBBR"의 불완전성은 3이다. "BB"가 1번, "RR"이 2번 등장했기 때문이다. 우리의 목표는 불완전성이 최소가 되도록 빈 타일을 색칠하는 것이다. Input 첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 100)$ 이 주어진다. 각 테스트..
알고리즘/codeforces
Codeforces Round #738 (Div. 2)-A. Mocha and Math
문제 설명 고등학생 지영은 학교 수학 선생님한테 매우 흥미로운 지식을 배우고 있다. 그 지식은 이진수와 이진수의 연산이다. 지영이에게 길이가 $n$인 수열 $a$이 주어진다. 지영은 무작위 구간 $[l, r]$을 선택해서 모든 $i (0 \le i \le r - l) $에 대해 $a_{i + 1}$을 $a_{i + 1} \wedge a_{r - i}$ 로 바꾸는 작업을 해야한다. 이때 $ \wedge$ 는 비트끼리 and 연산을 하라는 기호이다. 이 작업은 몇번이고 반복해도 상관 없다. 예를 들어 $n = 5$이고 배열이 $[a_1, a_2, a_3, a_4, a_5]$일 때, 지영이 구간 [2, 5]를 선택한다면 새로운 배열은 $[a_1, a_2 \wedge a_5, a_3 \wedge a_4, a_4..
