알고리즘/codeforces
Codeforces Round #744 (Div. 3)-B. Shifting Sort
문제 설명 차세대 외부 메모리에는 정수의 배열 $a[1...n] = [a_1, a_2, ..., a_n]$이 포함되어 있다. 이 종류의 메모리는 배열의 원소를 바꿀수가 없게 만들어졌다. 대신에 주어진 배열의 일부분을 자르고, 그 부분에 있는 원소들을 주어진 offset만큼 원형 이동시킨다. 기술적으로 각 원형 이동은 두가지 연속적인 단계로 이루어진다. 임의의 위치 $l$과 $r (1 \le < r \le n)$을 선택한다. $a[l...r]$ 부분을 왼쪽으로 임의의 offset $d$만큼 원형 이동 시킨 결과로 바꾼다. 원형 이동이란 다음 설명으로 이해할 수 있다. 순열 $[1, 4, 1, 3]$은 $[3, 1, 4, 1]$을 offset 1만큼 왼쪽으로 원형 이동 시킨 결과이다. 순열 $[4, 1, 3..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-A. Casimir's String Solitaire
문제 설명 시저는 대문자 'A', 'B', 'C'로만 이루어진 문자열 $s$를 생각하고 있다. 각 차례마다 다음 두 행동을 하나 선택해서 할 수 있다. 임의의 위치에 있는 문자 'A'와 문자 'B'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.) 임의의 위치에 있는 문자 'B'와 문자 'C'를 동시에 제거한다.(이 문자는 인접할 필요가 없다.) 따라서 문자열의 길이는 차례가 한번 지날때 마다 2씩 줄어든다. 예를 들어 $s$ = "ABCABC"가 있을 때 시저는 한 차례가 지난후 $s$ = "ACBC"를 얻을 수 있다. (첫번째 등장하는 'B'와 두번째 등장하는 'A'를 제거한다.) 우리가 해야할 일은 문자열 $s$가 주어졌을 때, 위에서 말한 행동을 차례차례 진행해서 빈 문자열을 만들 수 있는지 ..
알고리즘/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
