To the Expert

문제 설명 문자 a와 b로만 이루어져 있는 길이가 $n$인 문자열 $s$가 주어진다. $AB(s)$를 $s$의 substring 인 ab의 출현 횟수라고 하고, $BA(s)$를 $s$의 substring 인 ba의 출현 횟수라고 하자. 한 단계에서 우리는 index $i$를 선택하고 $s_i$를 문자 a나 b로 바꿀 수 있다. $AB(s) = BA(s)$ 가 되기 위해서 필요한 최소 연산은 무엇일까? Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 문자열 $s (1 \le |s| \le 100)$ 가 주어진다. 이때 $|s|$ 는 문자열 $s$의 길이를 의미하고 이 문자열은 a와 b로만 이루어져 있다. ..

AtCoder Beginner Contest 205 A부터 D까지 업솔빙 이번 대회 문제 set은 전체적으로 평이하다. 마지막 문제에 조금 헤맸는데, 분명 대회때는 TLE가 나와서 이 문제를 못풀었다고 생각했는데 대회 결과를 보니까 4솔로 되어있어서 이상했다. 결과를 보니 대회에서 제공하는 testcase는 모두 통과했는데, virtual에서 제공하는 test case는 통과못해서 그런 결과가 나온것 같다. 하지만 TLE가 나온것은 TLE이기 때문에 틀렸다고 생각하고 업솔빙을 했다. 이번 대회를 참여하면서 배운 것은 std::lower_bound()의 활용 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - kcal (*6) 접기/펼치기 문..

문제 설명 카파와 수아는 정수 배열을 선물받았다. 카파는 숫자 $0$을 싫어하기 때문에 카파는 배열에서 $0$을 다 버려버렸다. 그 결과 길아기 $n$인 배열 $a$를 얻었다. 수아는 반대로 숫자 $0$을 좋아하기 때문에 $0$을 제외한 숫자로만 이루어져 있는 배열을 보고 화가 났다. 수아를 응원하기 위해서 카파는 길아가 $n$인 또 다른 배열 $b$를 생각해 냈다. 이 배열은 $\sum_{i=1}^{n} a_i \cdot b_i = 0$ 을 만족한다. 카파는 숫자 $0$을 싫어하기 때문에 배열 $b$는 숫자 $0$이 포함하면 안된다. 또한 숫자는 반드시 크면 안된다. 따라서 배열 $b$ 원소의 절대값의 총합이 $10^9$를 넘어가면 안된다. 위의 조건을 만족하는 배열 $b$를 찾을 수 있도록 도와주자...

문제 설명 카파 할머니는 스카프를 짜기로 하셨고 수아 할머니에게 패턴을 짜달라고 부탁하셨다. 패턴은 영어 소문자로 이루어진 문자열인데, 수아 할머니는 길이가 $n$인 문자열 $s$를 적었다. 카파 할머니는 스카프를 아름답게 만들고 싶은데 할머니의 생각으로는 문자열 패턴이 팰린드롬으로 이루어져야만 스카프가 아름답다고 말한다. 카파 할머니는 수아 할머니가 쓴 패턴을 바꾸고 싶은데, 수아 할머니를 기분나쁘게 하지 않기 위해서 영어 소문자 하나를 정하고 그 문자만 문자열에서 제거하기로 했다. 이때 문자를 제거하는 수는 몇개든지 상관 없다. 한번도 제거 안할 수 있고 다 제거할 수도 있다. 카파 할머니는 패턴에서 제거해야할 문자의 수를 최소화 하고 싶다. 할머니를 위해 문자열 $s$가 팰린드롬이 되기 위해서 제거..

문제 설명 루나는 아침 산책을 가다가 길이가 $n$인 배열 $a$를 발견했다. 그는 배열의 모든 원소 총합인 $s$를 계산했다. 루나는 $a$의 부분 수열의 합이 $s - 1$인 경우 이 부분수열을 거의 완벽하다고 정했다. 루나는 배열 $a$의 거의 완벽한 부분 수열의 개수를 알고 싶어졌다. 그러나 집에 올때 까지 풀지 못했고, 우리의 도움이 필요하다!. 수열 $y$에 있는 원소를 지운 결과 수열이 $x$라면 수열 $x$는 수열 $y$의 부분수열이다. 이때 원소는 다 지워도 되고, 하나도 안지워도 된다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 배열의 길이 $n (1 \le n \le 60)$ 가..

문제 설명 루나는 콘서트장에서 노래를 부르기로 결정했다. 루나는 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)$ ..

문제 설명 크기가 $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를 이용해서 만들 수..

문제 설명 $n$명의 사람들이 참여하는 동아리 연합회의 중요한 회의가 개최됐다. 어떤 두 사람은 잠시 사적인 대화를 할 수 있다. 한 회의에서 두 사람은 계속 이야기 할 수 있다. 각 사람은 사교성이라는 지표를 가지고 있다. $i$번째 사람의 사교성은 음이 아닌 정수 $a_i$이다. 이 사교성의 의미는 정확히 $a_i$번 대화를 다 하면 회의를 떠나야 한다는 뜻이다. 그리고 그 사람은 더이상 아무와도 이야기할 수 없다. 만약 $a_i = 0$이면 $i$번째 사람은 시작하자마자 회의를 떠나야한다. 한 회의 안에서 주고받는 대화의 수가 가장 많은 경우 그 회의는 생산적이라고 말한다. 당신에게 사교성의 배열 $a$가 주어진다. 우리가 구해야할 것은 하나의 회의에서 사람들이 대화를 한 총 개수를 최대로 만들기 ..

문제 설명 지니는 $n \times m$ 크기 격자무늬가 그려진 직사각형을 가지고 있다. 그 직사각형은 처음에는 모두 흰색으로 색칠된 상태이다. $i$번째 행과 $j$번째 열을 위치로 가진 격자 부분을 $(i, j)$라고 적자. 가장 위쪽 행에서 가장 왼쪽 열 부분을 $(1, 1)$, 가장 아래쪽 행에서 가장 오른쪽 열 부분을 $(n, m)$이라고 하자. 지니는 직사각형에 각각 다른 크기의 V모양을 그리고 싶다. 크기가 $d (d > 0)$인 V모양을 그리는 방법은 격자 $(i, j)$를 다음과 같이 칠하면 된다. 먼저 중앙 격자 $(i, j)$를 검은색으로 칠한다. 그리고 정확히 $d$개의 격자를 좌상향 대각선 방향으로 검은색으로 칠하고, 정확히 $d$개의 격자를 우상향 대각선 방향으로 검은색으로 칠한..

문제 설명 차세대 외부 메모리에는 정수의 배열 $a[1...n] = [a_1, a_2, ..., a_n]$이 포함되어 있다. 이 종류의 메모리는 배열의 원소를 바꿀수가 없게 만들어졌다. 대신에 주어진 배열의 일부분을 자르고, 그 부분에 있는 원소들을 주어진 offset만큼 원형 이동시킨다. 기술적으로 각 원형 이동은 두가지 연속적인 단계로 이루어진다. 임의의 위치 $l$과 $r (1 \le < r \le n)$을 선택한다. $a[l...r]$ 부분을 왼쪽으로 임의의 offset $d$만큼 원형 이동 시킨 결과로 바꾼다. 원형 이동이란 다음 설명으로 이해할 수 있다. 순열 $[1, 4, 1, 3]$은 $[3, 1, 4, 1]$을 offset 1만큼 왼쪽으로 원형 이동 시킨 결과이다. 순열 $[4, 1, 3..