카테고리 없음
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
카테고리 없음
Codeforces Round #751 (Div. 2)-B. Divine Array
문제 설명 승현이는 $n (1 \le n \le 2000)$개의 정수로 이루어진 성스러운 배열 $a$ 을 받았다. $a$의 각 위치는 초기값을 가지고 있다. 그런데 갑자기 배열에 저주가 내려졌다!! 배열은 화가났고, 멈추지않는 변환이 시작되었다. 변환은 무한번 이루어지는데, 배열 $a$는 다음 방식으로 $i$번째 단계를 수행한다. 모든 주어진 위치 $j$에 대해서 $a_j$는 이 단계를 수행하기 전에 배열 $a$에 있는 $a_j$의 개수로 바뀐다. 당신이 문제를 잘 이해하기 위해서 예시를 들어보자면. 초기단계 $2, 1, 1, 4, 3, 1, 2$ 첫번째 단계 이후 $2, 3, 3, 1, 1, 3, 2$ 두번째 단계 이후 $2, 3, 3, 2, 2, 3, 2$ 세번째 단계 이후 $4, 3, 3, 4, 4..
알고리즘/codeforces
Codeforces Round #751 (Div. 2)-A. Two Subsequences
문제 설명 승현이에게 문자열 $s$가 주어진다. 우리는 다음 조건을 만족하는 비어있지 않은 두 문자열 $a$, $b$를 찾아야한다. 문자열 $a$와 $b$는 모두 $s$의 부분 문자열이다. 각 인덱스 $i$에 대해서 문자열 $s$의 문자 $s_i$는 반드시 문자열 $a$와 $b$ 둘중 하나에만 포함되어야 한다. 문자열 $a$는 가능한 사전적으로 작은 문자열이어야 한다. 그리고 $b$는 가능한 아무 문자열이라도 상관없다. 문자열 $s$가 주어졌을 때, 가능한 $a$와 $b$를 출력한다. Input 첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다. 각 테스트케이스의 첫번째 줄에는 문자열 $s (2 \le |s| \le 100)$가 주어진다. 문자열 $..
