Codeforces Round #802 (Div. 2)

https://codeforces.com/contest/1700

Dashboard - Codeforces Round #802 (Div. 2) - Codeforces

올라가자..

 

 

A (00:02)

오른쪽 끝까지 이동 -> 그대로 아래로 쭉 이동

 

B (00:15)

앞자리가 9인 경우: 11111111 (자리수 + 1)

앞자리가 9가 아닌 경우: 99999999

 

C (00:25)

왼쪽부터 진행해도 최적이다. \(A_i\)와 \(A_{i+1}\)의 대소관계에 유의하여 풀면 된다.

 

D (01:10)

열린 파이프의 개수를 k라고 하자. (sum(A) / k)를 올림한 값이 곧 걸리는 시간이다. 이분 탐색이 마려워진다.그러나, 4 1 1 1 1이고, 열린 파이프의 개수가 4인 경우는, 2초가 아닌 4초가 걸리는데, 오른쪽에서 왼쪽으로 물이 넘어가는 것은 아니므로, 1~X번째에서 X개의 열린 파이프가 있을 때 채워지는 시간은 dp로 처리해주면 된다. (sum(A) / k)와 dp[k] 중 최댓값으로 이분 탐색을 하면 된다.

 

E (--:--)

1을 2 주위로 이동

n을 n-1 주위로 이동

x -> x+1의 경로가 없다고 할 때,

x를 x + 1주위로 이동

x + 1을 x 주위로 이동

으로 하면 답이 1인 경우에 확인할 수 있을 것 같다고 생각을 했는데, 이게 맞는지도 모르겠고, 시간도 없어서 구현을 못 했다.

 

F (--:--)

업솔빙했다. 다른 코포 라운드에서 본 적이 있는 문제다. 첫번째 줄과 두번째 줄을 나누고 오른쪽으로 옮기는 경우와 왼쪽으로 옮기는 경우를 그리디하게 처리해주면 된다.

https://www.acmicpc.net/problem/16983

16983번: Coin Collecting

동일한 아이디어를 사용하는 문제이다.