#709 div2 03/21

 

링크는 대회 조회가 불가능해서 스킵

 

A

 

오랜만에 그 절대 집중 안되는 모드가 찾아왔다. A지문을 한 다섯 여섯번 읽어도 무슨 소리인지 모르는 뇌와 눈의 불협화음이라고 해야되나 암튼 그렇게 헤매다가 지문을 이해했는데 모든 칸이 밖으로 연결되어야 한다는 소리여서, 무조건 최소 하나씩의 벽을 허물면 가능

 

10분 솔브

 

B

 

어떤 수열이 있는데, 그 수열이 어떤 식을 만족하느냐 아니냐, 그리고 그 때에 만족하는 최대 m과 어떤 c값이 무엇이냐 구하는 문제였다. 

 

우선 m은 주어진 수열의 최댓값보다 최소 1이상 큰 수이다. 왜냐면 그 수열은 m으로 %한 수들이기 때문에 0~m-1값을 갖는다. 이 식이 지금 생각해보니 필요한지는 몰라도 

 

그리고 만약 오름차순의 부분 수열이 존재한다면 그 차이의 값이 c이고, 그 값은 그 수열에서 유일하다. 만약에 한 수열에서 여러개의 c값을 갖는다면 불가능 

 

이제 c값을 구했으니, 최대 m을 구하면 된다. c값이 고정되있는 상태에서 m값은 모든 수열에서 i-(i-1)에서의 값이 기울기가 같으면 무한대로 가능하고 그렇지 않으면 하나의 값을 갖는다. m이 하나의 값이 아니라 여러개의 값이 나온다면 불가능 

 

생각 -> 구현이 너무 빡셌다. 

 

1시간 40분 솔브

 

C

 

n명의 사람이 m일 일하는데 하루에 한 명 일하고, 날마다 일 할수 있는 사람들의 명단이 주어진다. 

그래서 어떠한 사람도 (m+1)/2 이상의 날을 일하지 않게 가능한지 구하고 그 날마다 누가 일할지 명단 작성하는 문제

 

먼저 dp인줄 알았다. 그냥 뭔가 dp느낌 하지만 그리디 향기가 났고, 

 

요일을 일하는 사람명수대로 정렬을 하고, 그리고 거기에서 가장 적게 일할게 남은 사람을 쓰면 된다고 생각을 했다. 

 

하지만 그 요일과 명수의 값에 대한 관리를 어떻게 해야할지 잘 모르겠었고, 그 상태에서 (m+1)/2 이상인 날이 있는지 없는지 확인을 한 상태에서 그게 최적이라는 보장도 없어서 그냥 구현에 대한 생각만 하다가 끝

 

킹갓제네럴 Green55님이 깔끔하게 증명한걸보고 감탄