알고리즘/atcoder
AtCoder Beginner Contest 204 - A부터 D까지 업솔빙
AtCoder Beginner Contest 204 A부터 D까지 업솔빙 atcoder의 문제 수준에 갈수록 놀라면서 문제를 풀고 있다. 확실히 플랫폼이 달라서 그런지 출제되는 문제 유형도 확연하다고 느낀다. 하지만 여기서 배운 방식을 codeforces에서 쓸 수 있을 것 같다는 생각이다. 근데 codeforces에서 푼 문제는 글쎄? atcoder에서 쓸 수 있을까? 아직은 dp가 어렵기 때문에 그것은 지켜봐야할 문제인 것 같다. 이번 대회를 참여하면서 배운 것은 냅색 알고리즘의 변형 문제 문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다. A - Rock-paper-scissors (*7) 접기/펼치기 문제 설명 사과, 오렌지, 포도는 가위바..
알고리즘/codeforces
Codeforces Round #748 (Div. 3)-E. Gardener and Tree
문제 설명 트리는 방향이 없고 사이클이 존재하지 않는 연결된 그래프이다. 이 문제는 root 노드가 존재하지 않는 트리를 다룬다. 트리의 리프노드는 최대 1개의 노드로만 연결된 노드를 말한다. 정원사 수호는 $n$개 노드를 가진 트리를 가꾼다. 그는 트리를 다듬기로 결정했다. 트리를 다듬기 위해서 그는 몇몇 연산을 수행해야 한다. 하나의 연산에서 그는 트리에 있는 모든 리프노드를 지운다. 이 문제의 특별한 경우 몇가지가 있다. 빈 트리에 연산을 적용하면, 혹은 노드가 한개도 없는 트리에 연산을 적용하면 변하지 않는다. 한개의 노드만 남은 트리에 이 연산을 적용하면 이 노드가 사라진다.(이 노드는 리프노드로 간주된다.) 두 노드로 이루어진 트리에 이 연산을 적용하면 두 노드가 같이 사라진다. (두 노드 모..
알고리즘/codeforces
Codeforces Round #748 (Div. 3)-D1. All are Same
문제 설명 요한은 정수 $a_1, a_2, ..., a_n$으로 이루어진 길이가 $n$ ($n$은 짝수이다.)인 배열을 가지고 있다. 요한은 양의 정수 $k$를 생각해냈다. 그 후 배열에 다음 연산을 수행했다. 인덱스 $i (1 \le i \le n)$ 를 선택하고 숫자 $a_i$에 $k$를 뺀다. 이러한 연산을 한번도 수행하지 않거나 한번 이상 수행하고 나서 배열에 있는 모든 원소가 같은 수로 만들고 싶다. 배열에 있는 모든 원소가 같은 수로 만들기 위해서 필요한 최대 $k$값을 구하자. 만약 이 숫자가 무수히 존재하면 $-1$ 을 출력한다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 숫자 $n$ (..
알고리즘/codeforces
Codeforces Round #748 (Div. 3)-C. Save More Mice
문제 설명 고양이 한마리와 쥐 $k$마리가 있다. 그리고 수직선에 구멍 하나가 있다. 고양이는 $0$번 지점에 위치해있고 구멍은 $n$번 지점에 위치해있다. 모든 쥐는 고양이와 구멍 사이에 위치해 있다. $i$번째 쥐는 $x_i (0 t; while(t--){ int n, k; cin >> n >> k; int arr[k]; for(int i = 0; i > arr[i]; sort(arr, arr + k, greater()); int sum = 0, ans = 0; for(int i = 0; i = n) break; ans++; } cout
알고리즘/codeforces
Codeforces Round #748 (Div. 3)-A. Elections
문제 설명 세 후보자가 지원한 선거가 방금 끝났다. 첫번째 후보자는 득표수가 $a$이고, 두번째 후보자는 득표수가 $b$이고, 세번째 후보자는 득표수가 $c$이다. 각 후보자에 대해서 다음 문제를 풀어보자. 각 후보자가 선거에서 승리하려면 몇개의 득표수를 더 받아야 할까? 즉 각 후보자가 다른 후보자들의 득표수 보다 크기 위한 득표수를 구해야 한다. 각 후보자에 대해 이 문제는 독립적으로 풀어야 한다는 것을 잊지 말자. 한 후보자가 우승하기 위해서 추가된 득표수는 다른 두 후보자가 우승하기 위해서 추가된 득표수를 구할때 반영되지 않는다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 10^4)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 세 정수 $a, b..
알고리즘/atcoder
AtCoder Beginner Contest 202 - A부터 D까지 업솔빙
AISing Programming Contest 2021（AtCoder Beginner Contest 202） A부터 D까지 업솔빙 세번째로 풀어본 Atcoder 문제셋이다. A번 문제와 B번 문제는 너무 쉬워서 그냥 넘어가고, C번 문제에서 조금 시간을 끌었지만 한번 푼 이후로는 다시 안틀릴 거 같은 문제였다. 그리고 대망에 마지막 D번 문제, 맨날 코드포스만 연습하느라 DP관련 문제를 잘 안풀었는데 이 문제가 내 감각을 다시 일께워 준것 같아서 못풀었지만 업솔빙하면서 기분이 좋았다. 개인적으로 업솔빙을 잘했다고 느낀 문제는 이 문제가 처음이었다. 이번 대회를 참여하면서 배운 것은 다이나믹 프로그래밍 점화식 짜기 복습 파스칼의 삼각형과 다이나믹 프로그래밍의 관계 조합론 문제 옆에 붙어있는 난이도는 At..
