[Codeforces] Round #459 (Div. 2)

http://codeforces.com/contest/918

 

2문제밖에 풀어내지 못했습니다ㅠㅠ 평소의 Div 2에 비해 C가 살짝 어렵고 D가 살짝 쉬웠다곤 하는데 C에 모든 시간을 다 뺏겨서 D, E는 문제를 제대로 확인조차 못했네요. C는 5번의 Wrong Answer를 받았습니다.

 

A - Eleven

 

피보나치 값들을 미리 저장해두고 isFibo 함수를 만들어 풀었습니다.

 

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

 

B - Radio Station

 

map을 이용해서 ip를 key로, name을 value로 정해둬서 바로바로 꺼내썼습니다. 시간복잡도는 O(NlgNlgM)이지만 굳이 map을 쓰지 않고 배열로 저장해뒀어도 O(NM)이면 넉넉했을 것 같네요.

 

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

 

C - The Monster

 

기본적인 아이디어는 흔한 괄호쌍 문제처럼 (가 나오면 value를 1 증가, )가 나오면 value를 1감소시키고 ?가 나오면 다른 변수 q를 1 증가시킵니다. q는 value를 1 증가시키기 위해 쓰일 수도 있고, 1 감소시키기 위해 쓰일 수도 있을 것입니다. ')'로 바꾸거나 '('로 바꾸거나의 차이겠죠.

 

각 시작점에 대해(for st = 0; st < len; st++) 문자열을 차례로 확인하면서 value와 q를 하나씩 계산해나갑니다. 그리고 만약 value가 q보다 작아지는 때가 오면 q의 일부를 '('으로 바꿔야합니다.

 

예를 들어 ((???)) 일 경우, 마지막 ?를 읽어들일 때 val = 2, q = 3이 됩니다. 그러면 ? 3개중에 적어도 1개는 반드시 '('가 되어야 합니다.(만약 3개가 전부 닫는 괄호일 경우 value가 -1이 될테니까요.) 그러니 q를 1 감소시키고 val을 1 증가시킵니다. 이렇게 강제로 여는 괄호로 바꿔야하는 갯수는 (q-val+1)/2 입니다.

 

그런데 만약 val < q여서 ?를 여는 괄호로 바꿔주어야하는데 남아있는 물음표가 없으면 어떻게 될까요? ( ex : ??))) 에서 마지막 닫는 괄호를 읽어들일 때) 그러면 어떤 수를 쓰더라도 올바른 괄호쌍을 만들 수 없다는 것이니 다음 시작점으로 넘어가면 됩니다.

 

즉, 이중 for문을 돌면서 val과 q를 계속 계산해나갑니다. 그리고 현재 보고있는 문자열의 길이가 짝수이고, val이 q 이하일 경우 가지수를 1 증가시킵니다. 일부 케이스에 대해 st, i, val, q 값을 적어보면 아래와 같습니다.

 

??()??

st 0 i 0 val 1 q 0  st 0 i 1 val 1 q 1  got

st 0 i 2 val 2 q 1  st 0 i 3 val 1 q 1  got

st 0 i 4 val 2 q 1  st 0 i 5 val 2 q 2  got

st 1 i 1 val 1 q 0  st 1 i 2 val 2 q 0

st 1 i 3 val 1 q 0  st 1 i 4 val 1 q 1  got

st 1 i 5 val 2 q 1  st 2 i 2 val 1 q 0  st 2 i 3 val 0 q 0  got

st 2 i 4 val 1 q 0  st 2 i 5 val 1 q 1  got

st 4 i 4 val 1 q 0  st 4 i 5 val 1 q 1  got

7

 

?(?(

st 0 i 0 val 1 q 0  st 0 i 1 val 2 q 0

st 0 i 2 val 2 q 1  st 0 i 3 val 3 q 1

st 1 i 1 val 1 q 0  st 1 i 2 val 1 q 1  got

st 1 i 3 val 2 q 1  st 2 i 2 val 1 q 0

st 2 i 3 val 2 q 0

1

 

사실 맨 처음에는 val < q일 때 처리를 해야한다는 것을 모르고 val <= 0일 때만 처리를 하다가 여러 번 틀렸고, 반례를 뒤늦게 찾은 후에도 계속 코딩에서 실수를 해서 결국 맞추지 못했습니다ㅠ_ㅠ 대회가 끝나고 테스트케이스를 본 이후에야 잘못된 점을 찾아냈습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20459%20Div.%202/C.cpp

 

그나마 다행히 A, B 문제를 빠르게 풀어내어(A 3분 B 10분) 레이팅이 소량 상승하긴 했습니다.