[Codeforces] Round #519

http://codeforces.com/contest/1043

 

A부터 E까지 쭉 풀만했습니다. 잔실수를 많이 해서 코딩 속도가 평소보다 좀 느려진 것 같아 아쉬웠습니다.

 

A - Elections (Code)

 

그냥 k의 하한을 잡은 후에 1씩 증가해나가면서 조건을 만족하는 순간을 찾으면 됩니다. 

 

B - Lost Array (Code)

 

n이 1000 이하이니 l = 1, 2, ..., 1000까지 다 해보면 됩니다. 만약 n이 더 컸다면 kmp 등을 사용해야 했을 것입니다.

 

C - Smallest Word (Code)

 

직접 끄적거리다보면 aaaaa....aabbbb...bb꼴로 만들 수 있음을 알 수 있습니다. 적절하게 a끼리 모으고 b끼리 모을 수 있도록 답을 만들면 됩니다.

 

D - Mysterious Crime (Code)

 

문제 설명이 개떡같아서 시간이 좀 끌렸습니다. 우선 m개의 열에서 각 수가 어디에 등장하는지를 저장하는 inv 테이블을 미리 채워둡니다. 그리고 첫 번째 행의 각 원소에 대해, 해당 원소가 어디까지 이어질 수 있는지를 보면 됩니다. 최대 m개의 원소를 살피고 나면 다음 원소로 갈 수 있으니 $O(NM)$에 풀이가 가능합니다.

 

E - Train Hard, Win Easy (Code)

 

우리는 같이 팀이 될 수 없는 조건을 무시한 채 한 학생이 이루는 팀의 점수의 합을 구할거고 나중에 u, v를 통해 낮아지는 점수를 빼줄 것입니다.(이건 u, v를 입력받는 족족 바로 빼놓으면 됩니다.) 이제 팀의 점수의 합은 x-y 기준으로 정렬을 해놨을 때, 각 학생에 대해 내 앞의 학생들은 x를 더해주면 되고 내 뒤의 학생들은 y를 더해주면 됩니다. 이를 prefix sum으로 O(1)에 바로 구해주면 됩니다.