[2017-09-25] Codeforces Round #436 (Div. 2)

링크 : http://codeforces.com/contest/864

문제도 쉬웠고 잘 풀려서 프리테스트까지는 14~5등 정도였는데 C번에서 진짜 멍청한 실수를 해가지고 시스템 테스트에서 나가는 바람에 153등으로 미끄러졌다 ㅠㅠ 바로 퍼플 다시 복귀할 좋은 찬스였는데 참 아쉽. 코드포스는 할 때마다 내가 참 주의성 부족하게 코드를 짠다는 걸 느끼게 된다. 좀 더 엄밀하게 코드 테스트하는 습관을 들여야하는데...

A. Fair Game

문제 설명에 충실하게 짜기만 하면 된다.

B. Polycarp and Letters

이 문제도 그냥 맨 앞에서부터 주어진 문자열 따라가면서 문제 조건에 따라 처리해주면 그리 어렵지 않게 해결할 수 있다. A번도 그렇고 B번도 그렇고 요런 문제들은 풀이를 어떻게 설명해야 할 지... 차라리 코드로 보는게 풀이 이해가 더 빠를 것 같다.

C. Bus

주유소를 최대한 적게 써서 주어진 횟수만큼 왕복 가능한 지를 물어보는 문제인데, 왕복 불가능할 만큼 기름이 적게 남을 데까지는 주유 안하다가 왕복 불가능할 만큼 기름이 적게 남게 되면 그 때 채워주는 걸 반복해주면 된다. 왔다갔다하는 거리에 비례해서 기름이 소모되고 주유소 위치가 정해져 있기 때문에 이 주유소 그냥 지나치면 다음에 다시 돌아올 수 있는지 판별하는 건 간단한 수식 계산으로 쉽게 알 수 있고, 전체 k번 순회를 해야하기 때문에 k번 반복문 돌면서 똑같은 계산 시뮬레이션 해주면 되는데, k상한이 10000 밖에 안 되기 때문에 시간 안에 답이 잘 나온다. 

처음에 분명히 생각했던 예외 케이스였음에도 불구하고 풀면서 빼먹어가지고 시스템 테스트에서 틀렸다. ㅠㅠ 남들 코드 핵한다고 나서기 전에 내 코드부터 핵하고 락걸자 라는 생각이 들었다. 시스템 테스트에서 나간 거 보자마자 코드 다시 보니 바로 어디서 틀린 건지 알 수 있었기 때문에..

D. Make a Permutation!

주어진 수열에서 최소한의 개수의 숫자만 바꿔서 수열을 순열(1~n까지 숫자가 한 번씩만 나타나는 수열)로 바꾸고 싶은데 이 때 숫자 바꾸는 최소 횟수를 구하는 문제다. 일단 순열로 만들되, 가능한 순열이 여러 개가 있다면 사전순으로 가장 앞서게 만들어야 한다.

 나는 간단한 전처리를 한다음 맨 앞에서부터 현재 숫자를 바꿔야 할지 아닐지 확인하는 식으로 풀었는데, 만약에 기존 수열에서 하나밖에 안 남은 숫자라면 그 숫자는 바꾸면 안 된다(1~n사이 숫자가 한 번씩은 나와야되는데, 여기서 바꾸면 나중에 또 바꿔야 하기 때문에 바꾸는 횟수에서 손해봄). 또, 사전순으로 가장 앞서게 만들어야하므로 1~n숫자들 중 등장하지 않는 가장 작은 수부터 순서대로 나타나게 만들어줘야 하는데, 이 때 바꿀 수가 기존 수보다 더 크다면, 그리고 해당 바꿀려는 숫자가 기존 수열에서 2번 이상 등장한다면 현재 수를 놔두고 나중에 해당 수가 또 나울 때 거기서 바꾸는게 사전 순으로 더 앞이기 때문에 그렇게 해주고, 아니면 그냥 바로 바꿔주면 된다. 이 규칙 그대로 지키면서 전체 수열 처음부터 쭉 계산해주면 O(N)에 답을 구할 수 있다. 

E. Fire

n개의 물건이 있고 물건은 각각 ti, di, pi라는 세 가지 수치를 갖고 있다. 해당 물건을 지키기 위해 걸리는 시간이 ti, 그 물건이 타서 없어져버리는 데 걸리는 시간이 di, 물건의 가치를 pi라고 했을 때, 물건들 가치 합이 최대가 되게 구할려면 어떤 물건들을 구해야하는 지를 찾는게 문제다. 좀 까라도워 보이지만 타서 없어지는데 걸리는 시간 di를 기준으로 정렬하면 DP로 쉽게 구할 수 있다. 

 만약에 어떤 물건 집합 S를 선택하려고 했을 때, a,b라는 두 개의 물건에 대해 da < db라면 a를 먼저 구하는게 항상 이득이기 때문이다. b를 먼저 구할 경우 a가 타서 없어질 수 있지만 a를 먼저 구했는데 b가 타서 없어질 수는 없기 때문(a,b둘 다 선택이 가능하다고 했을 때). 즉 어떤 물건들에 대해서 di순으로 정렬해두면 항상 di가 더 작은 값부터 집합에 포함시킬 지 말지 고려하게 되므로 모든 경우를 다 테스트해볼 수 있다. di순으로 정렬한 다음에는 평범한 냅색 dp처럼 구현하면 된다. 시간 복잡도는 O(N(logN + D)). N이 100이고 D가 2000이므로 시간 제한안에 충분히 답이 나온다.