알고리즘/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 Round #748 (Div. 3)-B. Make it Divisible by 25
문제 설명 양의 정수 $n$이 주어진다. 한번의 연산으로 아무 자릿수를 하나 선택한 다음 그 수를 제거할 수 있다. 즉, 숫자에서 임의의 자리를 선택하고 그 자리에 있는 수를 제거한다. 이 연산은 자릿수가 1개 남아있을 때는 수행할 수 없다. 만약 남아있는 수가 0으로 시작한다면 자동으로 0은 사라진다. 만약 숫자 $32925$ 가 있을 때, 3번째 자릿수를 지운다면 $3225$가 된다. 만약 숫자 $20099050$ 의 첫번째 자릿수를 지운다면 $99050$ 이 된다. (두개의 0이 자동으로 지워진다.) $25$로 나누어 떨어지고 양수 로 만들기 위해서 필요한 최소 연산의 수는 몇개일까? 주어진 숫자에서 답은 항상 존재하고 주어진 숫자는 0으로 시작되지 않는것이 보장된다. Input 첫번째 줄에는 테스..
알고리즘/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..
알고리즘/codeforces
Codeforces Round #751 (Div. 2)-C. Array Elimination
문제 설명 음이 아닌 정수로 이루어진 배열 $a_1, a_2, ..., a_n$ 이 주어진다. 정수 $k (1 \le k \le n) $ 에 대해서 제거라는 연산을 다음과 같이 정의하자. 서로 다른 배열의 인덱스 $(1 \le i_1 t; while(t--){ int n; cin >> n; int arr[n]; for(int i = 0; i > arr[i]; int cnt[31] = {}; for(int i = 0; i
