[Codeforces] Round #584

https://codeforces.com/contest/1209

 

A - Paint the Numbers (Code)

 

Greedy하게 작은 수부터 체크하면서 지울 수 있는 수를 지워나갑니다.

 

B - Koala and Lights (Code)

 

주기가 대충 봐도 1, 2, 3, 4, 5의 공배수 정도일테니 넉넉하게 한 400까지 시뮬레이션 시키고 최적의 순간을 찾아냅니다.

 

C - Paint the Digits (Code)

 

잘 생각해보면 특정 수를 정했을 때 그 수 미만은 1, 그 수 초과는 2일 수 밖에 없음을 알 수 있습니다. 그리고 그 수는 상황에 따라 정해야합니다. 이를 0, 1, 2, 3, 4, 5, 6, 7, 8, 9에 대해 다 해보면 됩니다.

 

D - Cow and Snacks (Code)

 

문제를 잘못 읽고 이분매칭인줄 알았는데, 잘 생각해보면 특정 소가 원하는 snack 2개를 간선으로 연결했을 때 연결된 요소에 snack이 N개 있을 때 N-1마리의 소가 원하는 맛을 챙길 수 있음을 알 수 있습니다.

 

E1 - Rotate Columns (easy version) (Code)

 

그냥 뇌를 비우고 모든 경우를 다 쪼개어 해결하면 됩니다. row가 1일 때 max값을 구해야 하는데 모든 값을 더한 값을 출력해서 대회 중에 틀렸습니다;; hard version을 해결하기 위해서는 bitmask DP로 접근해야 합니다.

 

G1 - Into Blocks (easy version) (Code)

 

easy 버전은 그냥 특정 수가 예를 들어 3, 5, 6, 7번째에 나왔다고 치면 3번째부터 7번째까지의 수가 동일해야한다는 의미이니 이러한 구간들을 정렬해둔 후 합집합을 구하면 무조건 바뀌어야하는 원소의 갯수를 구할 수 있게 됩니다.

 

E1을 틀린게 너무 크리티컬했네요ㅜ