알고리즘/atcoder
AtCoder Beginner Contest 206 - A부터 D까지 업솔빙
AtCoder Beginner Contest 206 A부터 D까지 업솔빙 진짜 아쉬웠던 대회, 내 수준은 엣코더를 6번째 하면서 D번까지 풀면 실력이 오른거고 D번을 못풀면 실력이 아직 재자리라고 느끼는데 이번에는 접근 방법은 다 생각했는데 구현 방식을 몰라서 못풀었다. 이런 작동을 하는 효율적인 알고리즘이 무엇일까? 라는 생각의 답을 찾기 위해서는 다양한 variation의 문제를 풀면서 경험을 쌓는 수밖에 없다. 이번 대회를 참여하면서 배운 것은 Disjoint-Set(분리집합)의 find함수의 쓰임새 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Maxi-Buying (*5) 접기/펼치기 문제 설명 Atcoder 공화국에서는 소비..
알고리즘/codeforces
Educational Codeforces Round 116 - C. Banknotes
문제 설명 버클리음대에서는 $n$개 종류의 화폐를 사용하고 있다. $i$번째 타입은 $10^{a_i}$의 가치를 가지고 있다. 즉 첫번째 타입 화폐는 $1$원의 가치를 가지고 있다. $f(s)$를 정확히 $s$원을 내기 위해서 필요한 최소 화폐의 수라고 정의하자. 예를 들면 버클리음대에서 $1, 10, 100$원을 사용한다고 할 때 $f(59) = 14$ 이다. $1$원짜리 화폐 $9$개와 $10$원 짜리 화폐 $5$개로 최소 화폐 수로 $59$원을 낼 수 있기 때문이다. 그리고 이 방법 이외에는 더 적은 수로 화폐를 지불 할 수 없다. 정수 $k$에 대해서 화폐 개수가 $k$ 혹은 그보다 작은 화폐 개수로 낼 수 없는 최소 양수 $s$를 구하자. 즉 $f(s) > k$인 $s$를 구하는 것이다. Inp..
알고리즘/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$를 찾을 수 있도록 도와주자...
