알고리즘/codeforces
Codeforces Round #750 (Div. 2)-C. Grandma Capa Knits a Scarf
문제 설명 카파 할머니는 스카프를 짜기로 하셨고 수아 할머니에게 패턴을 짜달라고 부탁하셨다. 패턴은 영어 소문자로 이루어진 문자열인데, 수아 할머니는 길이가 $n$인 문자열 $s$를 적었다. 카파 할머니는 스카프를 아름답게 만들고 싶은데 할머니의 생각으로는 문자열 패턴이 팰린드롬으로 이루어져야만 스카프가 아름답다고 말한다. 카파 할머니는 수아 할머니가 쓴 패턴을 바꾸고 싶은데, 수아 할머니를 기분나쁘게 하지 않기 위해서 영어 소문자 하나를 정하고 그 문자만 문자열에서 제거하기로 했다. 이때 문자를 제거하는 수는 몇개든지 상관 없다. 한번도 제거 안할 수 있고 다 제거할 수도 있다. 카파 할머니는 패턴에서 제거해야할 문자의 수를 최소화 하고 싶다. 할머니를 위해 문자열 $s$가 팰린드롬이 되기 위해서 제거..
알고리즘/codeforces
Codeforces Round #750 (Div. 2)-B. Luntik and Subsequences
문제 설명 루나는 아침 산책을 가다가 길이가 $n$인 배열 $a$를 발견했다. 그는 배열의 모든 원소 총합인 $s$를 계산했다. 루나는 $a$의 부분 수열의 합이 $s - 1$인 경우 이 부분수열을 거의 완벽하다고 정했다. 루나는 배열 $a$의 거의 완벽한 부분 수열의 개수를 알고 싶어졌다. 그러나 집에 올때 까지 풀지 못했고, 우리의 도움이 필요하다!. 수열 $y$에 있는 원소를 지운 결과 수열이 $x$라면 수열 $x$는 수열 $y$의 부분수열이다. 이때 원소는 다 지워도 되고, 하나도 안지워도 된다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 배열의 길이 $n (1 \le n \le 60)$ 가..
알고리즘/codeforces
Codeforces Round #750 (Div. 2)-A. Luntik and Concerts
문제 설명 루나는 콘서트장에서 노래를 부르기로 결정했다. 루나는 1분짜리 노래 $a$개, 2분짜리 노래 $b$개, 3분짜리 노래 $c$개가 있다. 이 모든 노래를 두 콘서트에 각각 분배하고 싶다. 모든 노래는 무조건 두 콘서트중 하나에서 불러야 한다. 루나는 각 콘서트의 총 시간차를 가능한 한 최소화하고 싶다. 콘서트의 총 시간은 그 콘서트에서 부르기로한 모든 노래의 총 시간의 합이다. 각 콘서트의 최소 시간차를 출력해보자. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 각각 1분짜리 노래, 2분짜리 노래, 3분짜리노래를 의미하는 세 정수 $a, b, c (1 \le a, b, c \le 10^9)$ ..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-E1. Permutation Minimization by Deque
문제 설명 크기가 $n$인 순열 $p$가 있다. 비어있는 deque(double-ended queue)가 있다고 생각해보자. 큐는 원소를 큐의 앞과 큐의 뒤 모두 삽입이 가능한 자료구조이다. 따라서 만약 deque에 $[1, 5, 2]$가 순서대로 존재할때, 원소 $4$를 deque의 앞에 삽입하면 배열 $[4, 1, 5, 2]$가 만들어진다. 그리고 같은 원소를 이번에는 뒤에 삽입한다면 배열 $[1, 5, 2, 4]$가 만들어진다. 순열의 원소는 순서대로 $p_1$부터 시작해서 $p_n$까지 비어있는 deque에 삽입된다. deque에 원소를 삽입하기 전에 우리는 이 원소를 앞에 넣을지, 뒤에 넣을지 선택할 수 있다. 만약 순열 $p = [3, 1, 2, 4]$가 있을때, deque를 이용해서 만들 수..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-D. Productive Meeting
문제 설명 $n$명의 사람들이 참여하는 동아리 연합회의 중요한 회의가 개최됐다. 어떤 두 사람은 잠시 사적인 대화를 할 수 있다. 한 회의에서 두 사람은 계속 이야기 할 수 있다. 각 사람은 사교성이라는 지표를 가지고 있다. $i$번째 사람의 사교성은 음이 아닌 정수 $a_i$이다. 이 사교성의 의미는 정확히 $a_i$번 대화를 다 하면 회의를 떠나야 한다는 뜻이다. 그리고 그 사람은 더이상 아무와도 이야기할 수 없다. 만약 $a_i = 0$이면 $i$번째 사람은 시작하자마자 회의를 떠나야한다. 한 회의 안에서 주고받는 대화의 수가 가장 많은 경우 그 회의는 생산적이라고 말한다. 당신에게 사교성의 배열 $a$가 주어진다. 우리가 구해야할 것은 하나의 회의에서 사람들이 대화를 한 총 개수를 최대로 만들기 ..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-C. Ticks
문제 설명 지니는 $n \times m$ 크기 격자무늬가 그려진 직사각형을 가지고 있다. 그 직사각형은 처음에는 모두 흰색으로 색칠된 상태이다. $i$번째 행과 $j$번째 열을 위치로 가진 격자 부분을 $(i, j)$라고 적자. 가장 위쪽 행에서 가장 왼쪽 열 부분을 $(1, 1)$, 가장 아래쪽 행에서 가장 오른쪽 열 부분을 $(n, m)$이라고 하자. 지니는 직사각형에 각각 다른 크기의 V모양을 그리고 싶다. 크기가 $d (d > 0)$인 V모양을 그리는 방법은 격자 $(i, j)$를 다음과 같이 칠하면 된다. 먼저 중앙 격자 $(i, j)$를 검은색으로 칠한다. 그리고 정확히 $d$개의 격자를 좌상향 대각선 방향으로 검은색으로 칠하고, 정확히 $d$개의 격자를 우상향 대각선 방향으로 검은색으로 칠한..
