[Codeforces] Round #784 Div. 4

처음으로 올솔브를 했다 ! 매번 코포 치다가 일이 생겨서 점수가 바닥으로 고꾸라졌는데, 이번엔 제대로 집중해서 풀어봤다.

미끄럼틀

한 번도 안 틀렸어요

A. Division?

단순 조건문으로 판단한다.

B. Triple

$N <= 200,000$ 이라서 그만큼 배열을 만들어주고 카운팅한 다음에 3 이상인 것 하나를 출력한다.

C. Odd/Even Increments

짝수 인덱스를 모두 1씩 조절하거나, 홀수 인덱스를 모두 1씩 조절할 수 있다. 따라서 짝수 인덱스의 모든 값의 나머지가 같고, 홀수 인덱스의 모든 값의 나머지가 같아야 한다.

D. Colorful Stamp

W를 기준으로 나누었을 때, 각각 나눈 구역에 대해 B와 R이 하나라도 들어있으면 주어진 상태로 만들 수 있다. 모든 구역이 주어진 상태로 만들 수 있다면, 정답은 YES이다.

E. 2-Letter Strings

문자열들을 입력받고, 한 문자열과 그 뒤쪽에 위치한 문자열에 대해서 두 문자열이 한 자리만 차이나는 쌍의 개수를 구하는 문제이다.

입력에서 주어진 순서대로 앞글자와 뒷글자를 분리하고, 앞글자 개수 배열, 뒷글자 개수 배열을 만들었다. (defaultdict를 사용했다)

앞글자가 같다면 지금까지 해당 앞글자로 들어온 문자열의 개수를 더하고, 두 글자가 모두 같으면 안 되므로 두 글자가 모두 같은 경우를 빼면 된다. 뒷글자도 마찬가지로 구해주면 해결할 수 있다.

F. Eating Candies

왼쪽, 오른쪽에서부터 하나씩 더해가며 같을 경우에 정답을 갱신한다. 같다면 이전 정답보다는 큰 게 당연하니..

먹은 시점에서 왼쪽의 합이 크면 오른쪽을, 오른쪽의 합이 크면 왼쪽을 먹어나간다. 하나씩 먹으면서 진행하니 $O(N)$에 해결할 수 있다!

G. Fall Down

모든 열에 대해서 떨어뜨리는 작업을 수행하는데, 이는 다음과 같다.

- 맨 아래 행에서부터 시작해서, drop_row를 H-1로 설정한다

- 보고 있는 부분이 o 라면, drop_row를 하나 빼 준다.

- 보고 있는 부분이 * 라면, 떨어뜨린다. 단, drop_row와 현재 보고 있는 행이 같다면 떨어뜨리지 않는다. 떨어뜨린 뒤에는 drop_row를 하나 빼 준다.

- 빈 칸이면 건너뛴다.

H. Maximal AND

최대 $K$ 번의 OR operation을 할 수 있는데, 하나의 비트를 1로 바꿀 수 있다. 전체 수를 AND했을 때의 최대 수를 찾아야 하는 문제이다.

그리디하게 접근하자. 가장 왼쪽에 위치한 비트가 0인 수의 개수가 $K$ 보다 작다면, 해당 비트들을 모두 1로 바꿔주면 가장 큰 값을 만들 수 있다. 따라서 비트를 바꿀 수 있다면 모두 1로 바꾸고, $K$ 에서 빼주면 된다. 해당 작업을 31번 반복한 뒤, 모두 1인 비트의 수를 출력해주면 된다.

 

처음으로 문제를 다 풀었는데, 이번에 다 푼 참가자가 꽤 많다.. 1300명정도가 다 풀었는데 그 중에서 438등이면 꽤 빠르게 푼 것 같기도 하다.

딥3나 딥2를 더 많이 푸는 연습을 해야 할 텐데.. 다시 이름에 색깔 입히니 기분이 좋다