[Codeforces] Round #458 (DIv. 1 + Div. 2)

http://codeforces.com/contest/914

 

잘 풀린다 싶더니 정작 test에서 다 틀려서 딱 한 문제만 통과했습니다ㅠㅠ 그리고 처음으로 hack에 성공했습니다. 문제는 총 8문제, B는 Accepted, A C D는 정확한 풀이를 알고 있었으나 구현의 미숙으로 Wrong Answer(A C), Time limit exceeded(D)를 받았습니다.

 

A - Perfect Squares

 

그냥 거저 주는 문제인데 N = 0일 때를 예외처리를 해두지 않아 틀렸습니다. 마음이 아픕니다. 저는 혹시나 오차가 걱정되어서 sqrt를 사용하지 않았는데 hack할 때 보니 그냥 마음 편하게 sqrt를 사용한 사람들도 굉장히 많았습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20458/A.cpp

 

B - Conan and Agasa play a Card Game

 

귀납적으로 생각하면, 각 카드에 적힌 숫자가 전부 짝수번 등장하면 후수 필승, 어느 하나라도 홀수번 등장하면 선수 필승입니다. 이 문제에서 처음으로 hack을 성공했습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20458/B.cpp

 

C - Travelling Salesman and Special Numbers

 

operation을 한 번 적용하게 되면 그 즉시 값이 1000 이하로 줄어듬을 쉽게 알 수 있습니다. 그러면 이제 1000 이하의 값들에 대해서만 k 값을 미리 계산해두면 됩니다. 그러고나서 이제 구간을 나눠야하는데, 예를 들어 10010111 이하의 수들을 확인해야하면 범위를

00000000~01111111

10000000~10001111

10010000~10010011

10010100~10010101

10010110

10010111

로 나누는 것입니다. 이렇게 나누는 이유는 고정된 자리와 자유로운 자리를 구분해, 자유로운 자리 내에서 combination을 사용하기 위함입니다.

 

문제에서 나온 예제인 110 2로 간단하게 예시를 들어보면, 일단 구간을

000~011

100~101

110

으로 나눕니다. 각각의 구간에서 자유로운 자리는 2, 1, 0개 자리입니다.

 

각 구간에서 operation을 한번 적용한 결과가 2 4 8 16 .. 중 하나여야하는데 4 이상은 불가능하므로 우리는 1 2개를 놓기만 하면 됨을 알 수 있습니다.

 

첫 번째 구간 000~011에서, 자유로운 하위 2비트를 제외하면 고정된 곳에서 1이 없습니다. 2비트가 자유롭고 1을 2개 놓아야하므로 2C2 = 1입니다.

 

두 번째 구간 100~101에서, 자유로운 하위 1비트를 제외하면 고정된 곳에서 1이 1개 있습니다. 1비트가 자유롭고 1을 1개 놓아야하므로 1C1 = 1입니다.

 

마지막 구간 110에서 자유로운 비트는 없고 1이 2개 있습니다. 0비트가 자유롭고 0을 0개 놓아야하므로 0C0 = 1입니다

 

K = 0, K = 1일 떄 예외처리를 꼼꼼하게 했어야하는데 K = 1일 때 처리를 안해줬다가 틀렸습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20458/C.cpp

 

D - Bash and a Tough Math Puzzle

 

문제를 보자마자 Segment Tree라는 것이 감이 왔습니다. Segment Tree에는 구간의 gcd 값을 저장하고, 질의에는 일반적인 Segment Tree를 구할 때 처럼 따라 들어가는데, 조금 차이가 있다면 Tree의 값이 입력받은 x의 배수인지를 확인한다는 점입니다.

 

첫 번째로 꼭 x와 일치하지 않아도 괜찮고 x의 배수이기만 하면 된다는 점을 알아야합니다. x = 2가 들어왔는데 실제 gcd 값은 4라고 해봅시다. 그러면 그냥 어느 원소 하나를 2로만 바꿔주면 gcd값이 2가 됨이 보장되기 때문에 x의 배수이기만 하면 상관없습니다.

 

두 번째로 현재 보는 노드의 구간이 [l, r] 안에 포함되는 경우, 그 노드의 인덱스를 i라고 할 때 recursive하게 gcdquery를 call할 필요 없이 바로 2*i, 2*i+1의 값을 참조해 둘 다 x의 배수가 맞는지 아닌지를 확인하면 됩니다. 둘 다 x의 배수가 아니면 x의 배수가 아닌 원소가 구간 내에 적어도 2개 이상 있다는 의미니 2를 반환합니다.(저는 call을 했고 시간초과가 발생했습니다.)

 

이렇게 recursive하게 계산해 함수의 결과가 0 혹은 1이면 YES, 그렇지 않다면 NO입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20458/D.cpp

 

 

정말 많이 아쉽습니다. 코딩이 원래 그런거지만 A B D 모두 한 두 줄만 추가하거나 수정하면 맞는건데 문제 풀 때 부주의하게 풀다가 세 문제를 다 날려먹었습니다. 의미없는 가정이지만 네 문제 모두 정확하게 풀었다면 400위권 안에 들었을텐데 아쉽네요. Expert에서 강등당하려나 싶었는데 다행히 턱걸이로 살았습니다. 다음 라운드에는 정말로 꼼꼼하게 코딩을 해야겠습니다.