[Codeforces] Round #488 (Div. 1)

http://codeforces.com/contest/993

뭔가 잘 안풀렸습니다. C까지는 충분히 풀만했는데 A, B만 풀었을 뿐더러 둘 다 실수를 해서 불만족스러웠습니다.

A - Two Squares

좌표의 절대값이 100 이하이니 복잡하게 생각할 것 없이 그냥 미리 큰 board를 만들어 놓은 이후 사각형이 올라가는 격자점의 값을 바꿔서 겹치는 영역이 있는지 확인하면 됩니다. 마름모 내부에 정사각형이 있는 경우를 생각하지 못해 한번 틀리고, 좌표가 음수인 것을 생각하지 못해 hack을 당했습니다.

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

B - Open Communication

설명이 좀 더러워서 이해하는데 오래 걸렸습니다. 두 사람은 일단 0~9 사이에서 고유한 숫자 2개를 가지고 있습니다. 그리고 이 수들 중에서 겹치는 수가 1개 있습니다. 예를 들어 A는 3, 5를 가지고 있고 B는 0, 5를 가지고 있습니다. A가 2,4를 가지고 있고 B는 3,7을 가지고 있는 경우는 겹치는 수가 불가능합니다. 이제 두 사람이 통신을 통해 상대방과 자신 사이에 무슨 수가 겹치는지를 알고 싶어하는데, 문제는 '나'는 그 통신을 들여다볼 수 있습니다. 이러한 환경에서 두 사람은 여러 pair를 상대방에게 보내고 그 pair들 중 하나는 자신이 가진 pair임이 보장됩니다. 예를 들어 A는 3, 5를 가지고 있고 B는 0, 5를 가지고 있을 경우 A는 B에게 (6, 2), (3,5), (2,6), (3,1),(7, 2) 뭐 이런식으로 보낼 수 있습니다. 이 pair중 하나는 반드시 자신이 가지고 있는 pair입니다.

이제 '나'의 입장에서 두 사람 사이에 겹치는 수가 무엇인지를 알 수 있는가? 내가 두 사람 사이에 겹치는 수가 무엇인지는 몰라도 두 사람이 모두 겹치는 수를 알게 됐는가? 두 사람이 겹치는 수를 알지 못했는가?를 맞춰야합니다. 문제가 이해하기 힘들어서 그렇지 그냥 Case by Case로 계산을 하면 됩니다.

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

C는 충분히 풀만했는데 대회를 치룰 때 머리가 꼬여서 아예 이상하게 생각을 했네요. E는 FFT 문제인데 아직 FFT에 약해서 건들여보지 못했습니다.