알고리즘/codeforces
Codeforces Round #744 (Div. 3)-D. Productive Meeting
문제 설명 $n$명의 사람들이 참여하는 동아리 연합회의 중요한 회의가 개최됐다. 어떤 두 사람은 잠시 사적인 대화를 할 수 있다. 한 회의에서 두 사람은 계속 이야기 할 수 있다. 각 사람은 사교성이라는 지표를 가지고 있다. $i$번째 사람의 사교성은 음이 아닌 정수 $a_i$이다. 이 사교성의 의미는 정확히 $a_i$번 대화를 다 하면 회의를 떠나야 한다는 뜻이다. 그리고 그 사람은 더이상 아무와도 이야기할 수 없다. 만약 $a_i = 0$이면 $i$번째 사람은 시작하자마자 회의를 떠나야한다. 한 회의 안에서 주고받는 대화의 수가 가장 많은 경우 그 회의는 생산적이라고 말한다. 당신에게 사교성의 배열 $a$가 주어진다. 우리가 구해야할 것은 하나의 회의에서 사람들이 대화를 한 총 개수를 최대로 만들기 ..
알고리즘/codeforces
Codeforces Round #744 (Div. 3)-C. Ticks
문제 설명 지니는 $n \times m$ 크기 격자무늬가 그려진 직사각형을 가지고 있다. 그 직사각형은 처음에는 모두 흰색으로 색칠된 상태이다. $i$번째 행과 $j$번째 열을 위치로 가진 격자 부분을 $(i, j)$라고 적자. 가장 위쪽 행에서 가장 왼쪽 열 부분을 $(1, 1)$, 가장 아래쪽 행에서 가장 오른쪽 열 부분을 $(n, m)$이라고 하자. 지니는 직사각형에 각각 다른 크기의 V모양을 그리고 싶다. 크기가 $d (d > 0)$인 V모양을 그리는 방법은 격자 $(i, j)$를 다음과 같이 칠하면 된다. 먼저 중앙 격자 $(i, j)$를 검은색으로 칠한다. 그리고 정확히 $d$개의 격자를 좌상향 대각선 방향으로 검은색으로 칠하고, 정확히 $d$개의 격자를 우상향 대각선 방향으로 검은색으로 칠한..
알고리즘/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$개 노드를 가진 트리를 가꾼다. 그는 트리를 다듬기로 결정했다. 트리를 다듬기 위해서 그는 몇몇 연산을 수행해야 한다. 하나의 연산에서 그는 트리에 있는 모든 리프노드를 지운다. 이 문제의 특별한 경우 몇가지가 있다. 빈 트리에 연산을 적용하면, 혹은 노드가 한개도 없는 트리에 연산을 적용하면 변하지 않는다. 한개의 노드만 남은 트리에 이 연산을 적용하면 이 노드가 사라진다.(이 노드는 리프노드로 간주된다.) 두 노드로 이루어진 트리에 이 연산을 적용하면 두 노드가 같이 사라진다. (두 노드 모..
