[2017-10-16] Codeforces Round #441 (Div. 2)

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

5838점, 최종 순위 74위. 드디어 퍼플 복귀 가능할 듯! 간만에 잘쳐서 뿌듯한 대회였다. E번이 그리디하게 풀었는데 이게 답이 맞을 지 아닐 지 모르겠어서 시스템 테스트 끝날 때까지 전전긍긍하다가 결국 맞아서 너무 기분이 좋았다.

A. Trip For Meal

그리디 문제인데, 문제를 제대로 안 읽고 빨리 풀어서 냈다가 한 번 틀려서 50점 감점 먹었다. 나는 일일히 모든 경우를 다 테스트하는 식으로 풀었는데 다른 사람 풀이를 보니 a,b,c 세 개중 어떤게 최솟값이냐에 따라 한 번에 계산할 수 있는 방법이 있었다. 얼핏 그런 방법이 있지 않을까 생각은 했었는데 어차피 A번이고 빨리 푸는게 장땡일 것 같아 처음 생각난 풀이 그냥 바로 구현했는데, 좀 더 간결한 풀이를 생각하고 제출하는게 좋을지 A번 정도 쉬운 문제는 생각나는거 바로 구현해서 제출하는게 좋을지 잘 모르겠다.

B. Divisiblity of Differences

임의의 수 집합에서 부분 집합을 고르는데, 그 부분집합의 어느 두 원소를 골라도 차이가 m의 배수가 되게 고르되 부분집합의 크기가 k이상인게 존재하는지 묻는 문제이다. 알면 쉽고 모르면 어려운 부류의 문제인데 아무리 생각해도 얘가 C보단 어려운 문제인 것 같다. 실제로도 정답자 수가 C가 B보다 더 많다. 풀이는 주어진 원소를 m으로 나눈 나머지가 같은 애들끼리 묶고, 걔네들 중 크기가 k이상인거 아무거나 하나 골라주면 된다. m으로 나눈 나머지가 같으면 그 집합에서 어떤 두 원소를 꺼내도 반드시 차이가 m의 배수가 되기 때문이다. 유사한 문제가 꽤 있는데 하나라도 풀어봤으면 바로 풀이를 떠올릴 수 있는 부류의 문제.

C. Classroom Watch

어떤 수 k의 모든 자릿수 합을 d(k)라고 하자. 이 문제는 어떤 수 x가 주어졌을 때 k + d(k) = x가 되는 모든 k를 구하는 문제이다. 간단하게, 식을 변형하면 k = x - d(k)이고, 따라서 d(k)가 결정되면 k도 같이 결정된다. 가능한 d(k)가짓수가 x 최대 범위상 대충 100 안쪽이기 때문에, 자릿수합이 1인 경우부터 for문 돌려서 모든 경우 다 테스트해보고 저 식 만족하면 출력해주면 된다.

D. Sorting the Coins

 문제 지문이 너무 이해하기 힘들게 써 있어서 해석하는데 애를 많이 먹었다. 풀이도 대충 읽고 대충 생각하다가 말려서 중간에 계속 수정하느라 시간도 너무 많이 썼고.. O(NlogN) 풀이로 짰는데 나중에 온조님 풀이를 보니 O(N)으로 풀 수 있는 문제였다. O(N) 풀이 너무 깔끔해서 낙심.. 

 문제는 간단하게 요약하자면, 처음에 o가 N개 있는데, 걔네들을 전부다 특정한 순서대로 하나씩 x로 바꿀 것이다. 이 때 o,x로 구성된 어떤 문자열에 대해서, 1. 현재 문자가 o면 패스 2. 현재 문자가 x고 다음 문자가 o면 서로 교환. 을 처음 문자부터 순서대로 쭉 수행을 한다고 하자. 처음부터 문자 끝까지 순회하면서 저 동작을 하는 걸 1번의 순회라고 하고, 순회를 했는데 어떤 문자도 서로 교환되지 않으면 과정을 멈춘다. 이 때 주어진 첫 문자열에서 임의의 순서대로 각 원소를 x로 바꾸는 매 과정마다, 그 시점에서의 o,x로 구성된 문자열에 대해 저 동작을 총 몇 번 수행하게 되는지를 모두 출력하는게 문제다. 

 나는 x의 연속된 시퀀스를 모두 셋으로 관리하고 새로운 x가 추가될 때마다 셋에서 그 시퀀스 목록 갱신해주면서, 각 케이스에 대해 몇번 이동해야하는지도 같이 업데이트해주는 식으로 풀었다. 셋 관리때문에 O(NlogN)이 되는데, O(N)풀이는 각 시점에서 x가 하나 추가될 때마다 1씩 답을 더해주고, 맨끝부터 시작해서 x가 연속되는 구간 나올 때마다 왼쪽으로 o가 나올때까지 이동하며 답을 1씩 감소, 다시 그 위치에서 거기가 x로 바뀌면 똑같은 거 반복, ... 만 해주면 답이 나온다. 코드도 깔끔하고 짧고 실수할 여지도 적다. 좀 더 풀이를 깊이 생각하고 문제를 풀었어야했는데 싶은 생각이 들었다(맨날 하는 생각이지만...).

E. National Property

m개의 대문자와 m개의 소문자로 이루어진 언어가 있는데(각각 1' ~ m', 1 ~ m이라고 하자), 그 언어에서는 대문자가 무조건 소문자보다 앞에온다. 대문자/대문자, 소문자/소문자끼리는 값이 작은게 앞에 온다.

이 때 주어진 소문자로만 구성된 단어들에 대해서, 몇 종류의 소문자들을 모두 대문자로 교환해서(모든 단어에 나오는 모든 해당 소문자들을 다 대문자로 교환) 전체 단어 목록이 순서대로 사전순을 이루게 만들 수 있는 방법이 있는지를 묻는 문제이다. 2-sat으로도 풀린다고 하는데, 나는 2-sat 짤 줄 몰라서 그냥 그리디하게 짰다.

내가 생각한 방법은 간단하게 요약하면 '반드시 대문자로 바꿔야만 하는 문자를 전부 대문자로 바꾸는 걸 끝 문자까지 반복하고, 그 이후에 전체 목록이 사전순이면 ok, 아니면 불가능'이다. 이 문장은 당연히 참인데, '반드시 바꿔야만 하는' 것들을 전부 바꾸지 않으면 당연히 사전순이 아니고, 전부 바꿨는데 그 결과가 사전순이 아니면 당연히 이도 사전순이 아닌게 된다. 그러면 반드시 바꿔야 하는 경우를 바꿔주는 것만 정확히 수행할 수 있으면 답을 구할 수 있다는 이야기다.

나는 반드시 바꿔야 하는 경우를 이렇게 생각했는데, 임의의 i번째 위치에 대해 i-1번째까지 prefix가 같은 연속한 단어 집합에 대해서, i번째 위치에서 사전순이 어긋나게 되는(앞이 뒤보다 큰) 가장 마지막 위치 p를 먼저 구한다. 그러면 그 위치를 포함해서 앞에 있는 문자들은 전부 대문자가 되어야한다. 이는 귀납적으로 쉽게 알 수 있는데 사전순을 맞춰주려면 p번째 문자를 대문자로 바꿔야되고, 그러면 p-1번째 문자와 p번째 문자가 사전순이 어긋나게 되므로 p-1번째 문자도 대문자로 바꿔줘야 한다. 이를 쭉 반복하면 해당 그룹의 첫번째 문자부터 p번째 문자까지 전부 대문자로 바꿔야 한다. 

 그래서 이 과정을 제일 첫번째 문자부터 시작해서 맨 마지막 문자까지 전부 반복해주면서 반드시 대문자로 바꿔야하는 애들을 구하고, 그걸 다 대문자로 바꿨을 때 전체가 다 사전순이 만족되면 yes, 아니면 no로 진행해서 풀었다. 예외가 있을까 했는데 다행히 없어서 정답. 엄밀한 증명은 못 했지만 감이 맞아서 다행이라는 생각이 들었다. 복잡하게 짰는데도 불구하고 코딩 실수도 안했고...

F. High Cry

이 문제는 배점이나 정답자 수로 봐서는 E랑 별로 난이도 차이가 안 나는 문제인 것 같은데, 문제 읽어보지도 않고 대회 끝내버려서 나중에 한 번 읽고 풀이 생각이라도 해봐야 겠다.