전설로만 존재하는 줄 알았던 div. 4가 열린다길래 다른 일 다 뒤로 하고 보러 왔다.
난이도는 백준 기준으로 브론즈 4 ~ 실버 2? 정도 되는 거 같다.
가장 비슷한 사람의 퍼포를 보니 1800 정도 나오는 거 같다.
A - Division? [Solved!]
레이팅에 따라서 조건에 해당하는 Division을 출력하는 문제이다.
if문을 빠르고 정확하게 타이핑하자!
B - Triple [Solved!]
주어진 배열에서 같은 수가 3개 이상 나오는 수가 있는지 출력하는 문제이다.
파이썬 기준으로 Counter, dict, list 등을 사용해 배열에 존재하는 숫자의 개수를 세고 3개 이상이 있다면 출력하면 된다.
C - Odd/Even Increments [Solved!]
배열이 주어질 때 다음 연산을 0번 이상 수행한다.
- 홀수번째 요소에 1을 더한다.
- 짝수번째 요소에 1을 더한다.
연산을 적당히 수행한 후에 배열의 모든 요소의 홀짝이 같을 수 있는지 판별하는 문제이다.
초기 배열 상태에서 홀수번째 요소들끼리, 짝수번째 요소들끼리 홀짝이 같으면 YES를 출력하고 아니면 NO를 출력한다.
D - Colorful Stamp [Solved!]
처음에 n개의 W로 이루어진 문자열이 주어지는데 연속한 2개의 index를 골라 해당하는 부분을 BR, RB로 바꿀 수 있다.
이 연산을 여러 번 수행해서 입력받은 문자열로 만들 수 있는지 판별하는 문제이다.
W를 기준으로 분리한 다음 각 요소가 모두 같은 문자로 이루어져 있을 때만 NO를 출력하면 된다.
파이썬에 split()이라는 좋은 함수가 있다.
E - 2-Letter Strings [Solved!]
a~k로 이루어진 2자리 문자열이 $n$개 주어질 때 다음 조건을 만족하는 쌍의 수를 구하는 문제이다.
- $i<j$ 일 때 $s_i, s_j$는 정확히 한 자리만 같다.
번역기를 봐도 이해가 안 가고 해석도 힘들었던 문제였다..
우선 aa~kk까지 서로 다른 문자열의 개수가 $11^2 = 121$개이므로 모두 dict에 넣어서 개수를 셌다.(B번처럼)
그리고 2중 반복문을 돌면서 서로 다른 요소들의 곱을 구해줬다.
(C++에서 long long을 쓰라고 알려준다. 친절한 div 4)
F - Eating Candies [Solved!]
배열이 주어지고 한 명은 왼쪽에서 다른 한명은 오른쪽에서 출발하여 배열의 있는 값을 점수로 얻는다.
서로 같은 점수를 얻을 수 있는 최대 개수를 구하는 문제이다.
양방향누적합 + 이분탐색을 써도 되고 투포인터를 써도 된다.
투포인터로 접근하면 왼쪽 점수가 크면 오른쪽을 더하고 오른쪽점수가 크면 왼쪽을 더하는 식으로 접근한다.
누적합 + 이분탐색은 양방향 누적합을 구하고 1번 누적합의 요소가 2번 누적합의 요소에 있으면서 구간이 겹치지 않는지 확인하면 된다.
G - Fall Down [Solved!]
2차원 배열에서 돌이 장애물 만날 때까지 떨어진 상태를 구하는 문제이다.
배열 크기가 50x50이니 단순 시뮬레이션으로 구한다.
https://www.acmicpc.net/problem/13732
13732번: Falling Apples
The input begins with a line containing integers R and C, designating the number of rows and columns of the grid, such that 1 ≤ R ≤ 50 000 and 1 ≤ C ≤ 10. The first line is followed by R additional lines, each designating a row of the grid, from to
www.acmicpc.net
Falling Apples가 제한 50000에 실버4니까 얘는 실5 정도?
H - Maximal AND [Solved!]
배열에 다음 연산을 최대 $k$번 할 수 있다.
- $i$번째 요소에 $a_i | 2^j (0 \le j \le 30)$을 적용한다.
모든 연산이 끝난 후 배열의 모든 원소를 and한 값의 가능한 최댓값을 구하는 문제이다.
우선 배열의 모든 요소를 31자리 2진수로 바꾸고 각 자릿수에서 0의 개수를 센다.
큰 자릿수부터 반복하며 $k$ 보다 작거나 같으면 정답에 연산을 적용하고 $k$에서 해당 자릿수의 개수를 뺀다.
그 후 마지막에 정답에다가 모든 배열요소를 and하면 된다.
전형적인 코포식 비트마스킹문제
천상계사람들은 div2를 내가 div4 푸는 속도로 푼다는 걸 생각하니 정말 대단하다고 느낀다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 파이썬 dict, C++ map/unordered_map (0) | 2022.06.15 |
|---|---|
| [알고리즘] 고속 푸리에 변환(Fast Fourier Transform) part. 1 (0) | 2022.06.03 |
| [알고리즘] Codeforces Round #775 (Div. 2, based on Moscow Open Olympiad in Informatics) (0) | 2022.03.09 |
| [알고리즘] Codeforces Round #774 (Div. 2) (0) | 2022.03.05 |
| [알고리즘] 순열 사이클 분할 (0) | 2022.03.03 |