[Codeforces] Round #493 (Div. 1)

http://codeforces.com/contest/997

굉장히 오랜만에 친 코포네요. A, B 모두 빠르고 정확하게 잘 풀어냈습니다.

A - Convert to Ones

0의 묶음의 갯수를 k개라고 합시다. 예를 들어 1000100100에서는 0의 묶음이 3개이고 001000에서는 0의 묶음이 2개이고 010100100 에서는 0의 묶음이 4개입니다. 이 때 k >= 1일 경우 replace, opposite 연산을 합쳐서 k번 해야 전부 1로 만들 수 있습니다. 그리고 opposite는 최소 1번 이상 있어야 합니다.

replace, opposite 연산 중에 더 싼 것을 k-1번 하고, opposite를 1번 수행하면 됩니다.

https://github.com/blisstoner/Codeforces/blob/master/Round%20493%20Div.1/A.cpp

B - Roman Digits

문제는 곧 {a+5b+10c+50d | a+b+c+d = n}의 집합의 원소의 갯수를 의미하고, n이 작을 때에는 DP로 전수조사를 하면 됩니다. n이 클 경우에는 (b >= 1 && c >= 5) || (b >= 9) || (c >= 9) 인 경우는 고려할 필요가 없다는 것을 알아야합니다.(이미 다른 경우에 포함이 되므로) 

그렇다면 n+3 Combination 3 - n-3 Combination 3 - some constant가 되고, 계산해보면 49n-247 이라는 공식을 얻을 수 있습니다.

많은 사람들이 이 사실을 수학적으로 끄집어내기 보다는 그냥 대충 n<=100에 대해 계산을 해보고 규칙을 찾아 해결한 것 같습니다. 대회때 저는 좀 복잡하게 생각을 했고 코드도 다르게 짰는데 이해하기는 위의 풀이가 더 쉬울 것 같네요.

https://github.com/blisstoner/Codeforces/blob/master/Round%20493%20Div.1/B.cpp

두 문제 다 수학이 많이 쓰였네요.