알고리즘/codeforces
Educational Codeforces Round 116 - B. Update Files
문제 설명 버클리 음대에는 새 운영체제를 위한 업데이트 파일을 받았다. 처음에 이 파일은 $1$번째 컴퓨터에만 설치되어 있다. 업데이트 파일은 모든 $n$개 컴퓨터에 설치되어야 하는데, 컴퓨터는 인터넷에 연결되어 있지 않기 때문에 케이블을 이용해서 컴퓨터끼리 케이블을 연결해서 업데이트 파일을 받아야 한다. 오직 한 컴퓨터에는 한 케이블만 연결 될 수 있다. 따라서 업데이트 파일이 설치되어있는 컴퓨터가 다른 컴퓨터에 케이블로 연결되어서 업데이트 파일을 전송하는데 정확히 한시간이 걸린다. 우리가 해야할 일은 만약 버클리음대에 케이블이 $k$개 밖에 없는 상태에서 $n$개 컴퓨터가 모두 패치파일을 받기 위해서 걸리는 최소 시간을 구하는 것이다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $..
알고리즘/codeforces
Educational Codeforces Round 116 - A. AB Balance
문제 설명 문자 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
AtCoder Beginner Contest 205 - A부터 D까지 업솔빙
AtCoder Beginner Contest 205 A부터 D까지 업솔빙 이번 대회 문제 set은 전체적으로 평이하다. 마지막 문제에 조금 헤맸는데, 분명 대회때는 TLE가 나와서 이 문제를 못풀었다고 생각했는데 대회 결과를 보니까 4솔로 되어있어서 이상했다. 결과를 보니 대회에서 제공하는 testcase는 모두 통과했는데, virtual에서 제공하는 test case는 통과못해서 그런 결과가 나온것 같다. 하지만 TLE가 나온것은 TLE이기 때문에 틀렸다고 생각하고 업솔빙을 했다. 이번 대회를 참여하면서 배운 것은 std::lower_bound()의 활용 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - kcal (*6) 접기/펼치기 문..
알고리즘/codeforces
Codeforces Round #750 (Div. 2)-D. Vupsen, Pupsen and 0
문제 설명 카파와 수아는 정수 배열을 선물받았다. 카파는 숫자 $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$를 찾을 수 있도록 도와주자...
알고리즘/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)$ 가..
