Codeforces #582 (div 3) 후기

http://codeforces.com/contest/1213

작성일 : 190830

div3이라 쉬웠는데도 D번에서 아예 논리를 잘못 생각해서 말려버려서 좋은 결과는 내지 못했다.

A. Chips moving

결국에는 짝수번 움직일 때는 공짜고 홀수번 움직일 때는 1의 요금이 있으므로 전체 숫자 중 짝수와 홀수의 개수 중 min을 택하면 된다.

 

B. Bad prices

자기보다 더 싼 가격이 뒤에 있으면 bad price라는데 주어진 배열을 (index, price)로 저장한 후 price를 이용하여 정렬한 후에 앞에 indx보다 더 작은 값이 뒤에 가있으면 그거만큼 count해준다.

 

C. Book Reading

진짜로 1~n까지 m으로 나눠지는 것들의 digit을 일일이 구하면 망하는 문제. 힌트는 어떤 수든 10번만 반복되는 페이지를 구해보면 곱할때마다 1의 자리수는 매번 달라지므로 10번씩마다 그 합은 45가 된다(0~9까지의 합) 그걸 이용해서 전체 반복되는 횟수는 N/m/10이고, 이의 나머지는 N/m*10이니까 저 반복되는 배열을 부분합 배열로 구해서 전체를 구하면 됨.

 

D. Equalizing by division

배열이 주어지고 2로 나누는 연산을 여러 번 할 수 있는데 문제는 k개의 숫자를 똑같은 숫자로 만드는 데 필요한 연산의 횟수를 구해라고 한다.

결국에는 각 숫자에 대해서 대해서 2로 나누는 연산을 할 때마다 count를 늘려주고 해당 숫자가 몇 번 나눠줬을 때 나오는 지를 vector<int> v[1<<18]에 저장해준 다음에 그 숫자를 각각을 정렬해서 그 합을 구한 후 그 값을 전체에서 minimum을 구해주면 되는 것이다.

약간 log를 사용해서 빠르게 접근할 수 있지 않을까하고 문제를 좀 더 꼼꼼하게 읽지 않고 바로 코딩에 들어가서 시간을 다 써버렸다. ㅠㅠ