Codeforces Round #806 (Div. 4)

A. YES or YES?

code

문제 설명

입력으로 들어온 문자열이 대소문자 구분하지 않고 yes인지 확인하는 문제이다.

알고리즘

입력으로 들어온 문자열이 3글자인지 확인하고, 3글자라면 글자가 각각 y, e, s인지 확인한다.

B. ICPC Balloons

code

문제 설명

문자열로 팀이 어떤 문제를 풀었는지 입력으로 주어진다. (어떤 팀이 풀었는지는 의미가 없으므로 주어지지 않는다.) 문제를 풀면 풍선을 하나 주지만, 처음으로 문제를 풀면 풍선 두 개를 준다. 모든 팀이 받는 총 풍선의 개수를 출력해야 한다.

알고리즘

먼저 문자열의 길이 만큼의 풍선을 주게 된다.그리고 문자열에 있는 알파벳의 종류 개수만큼 추가적으로 풍선을 주게 된다.

C. Cypher

code

문제 설명

먼저 처음 자물쇠가 어떤 숫자로 적혀있는지 주어진다. 이 자물쇠의 각 자리는 0이상 9이하로, 돌리는 방식의 자물쇠이다.그 후, 각 자리수를 위로 또는 아래로 돌린다. 돌린 후 각 자리수를 출력하면 된다.

알고리즘

만약 위로 돌리면 숫자를 \( (a + 9) \mod 10 \), 아래로 돌리면 숫자를 \( (a + 1) \mod 10 \)으로 바꾼다.

D. Double Strings

code

문제 설명

총 \(n \le 10^5 \)개의 길이 8 이하의 문자열이 주어진다. \(n\)개의 문자열에 대해 각 문자열이 다른 두 개의 문자열을 이어서 만들 수 있는지 확인해야 한다.

알고리즘

문자열을 두 조각으로 쪼갠뒤 각 조각이 \(n\)개의 문자열 중에 확인하는 방식으로 확인할 수 있다. 문자열의 길이가 매우 짧기 때문에, \( 8n\log n \)안에 모든 문자열을 확인할 수 있다.

E. Mirror Grid

code

문제 설명

\(n \times n\)의 배열이 주어진다. 이 때, 최소 몇개의 숫자를 바꿔야 회전해도 숫자가 바뀌지 않는지 출력해야 한다.

알고리즘

\( (i, j)\)를 회전하면 \( (j - 1 - i, i)\)가 된다. 따라서 각 점에 대해 4번 회전한 뒤, 최소한의 횟수만으로 4개의 숫자를 똑같게 바꿔주면 된다.

F. Yet Another Problem About Pairs Satisfying an Inequality

code

문제 설명

길이 \(n \le 2\times 10^5\)의 배열이 주어진다. \(a_i < i < a_j < j\)를 만족하는 \(i, j\)의 개수를 출력해야 한다.

알고리즘

먼저 \(a_i \ge i\)인 원소는 무시한다. 이제 \(n\)번째 원소부터 \(1\)번째 원소 순으로 보면서 펜윅 트리로 특정 원소값의 개수를 관리한다. \(i\)번째 원소를 불 때, \(i+1\) 이상인 원소의 개수를 구하여 정답에 더해준 뒤, 펜윅 트리에 \(a[i]\)를 추가해주면 된다. 펜윅 트리는 1번부터 시작하므로, 입력되는 배열에 모두 1만큼 더한 뒤 계산하였다.

G. Good Key, Bad Key

code

문제 설명

총 \(n\)개의 상자가 주어진다. 1번 상자부터 차례대로 상자를 연다. \(i\)번째 상자를 열 때, \(k\)의 비용으로 좋은 열쇠를 쓰면 \(a[i]\)개의 동전을 얻지만, 공짜인 안좋은 열쇠를 쓰면 이번 상자를 포함하여 이후의 모든 상자에 있는 동전의 개수가 절반으로 줄어든다. 최대한으로 얻을 수 있는 동전의 개수를 출력해야 한다.

알고리즘

30번 이상 공짜 열쇠를 사용할 경우, 처음에 동전이 얼마있든 상관없이 이후의 상자에는 코인이 들어있지 않는다. 이를 이용하여 \(dp[i][j]=\) j번 공짜 열쇠를 사용해 i번째 상자까지 열어 얻을 수 있는 동전의 최대 개수로 정의하면 아래와 같은 점화식을 얻을 수 있다.

 

\( dp[i][j] = \max (dp[i - 1][j - 1] , dp[i - 1][j] - k) + \frac{a[i]}{2^j} \)\( dp[i][31] = \max (dp[i - 1][j - 1], dp[i - 1][j])

 

\(n\)개의 상자를 열어 얻을 수 있는 동전의 최대 개수는 \( \max (dp[n][i]) \)이다.