[Codeforces] AIM Tech Round 5

http://codeforces.com/contest/1028

 

일주일 전에 친 코포인데 이제야 글을 올리네요. A/B/C를 푼 후 G pretest를 맞고, 급하게 D를 풀었으나 맞추지 못했습니다. 그리고 G는 system test에서 터졌습니다 ㅠ_ㅠ

 

A - Find Square (Code)

 

(0,0)부터 차례로 보면서 B를 하나 찾기만 한다면 B가 각각 가로/세로로 몇 개까지 연속해있는지를 보면 됩니다.

 

B - Unnatural Conditions (Code)

 

그냥 합쳐서 $10^N$ 꼴이 되게하고 자기 자신은 자리수의 합이 굉장히 큰 수를 택하기만 하면 됩니다. 저는 555555555...55, 4444444444....45를 택했습니다. input 자체가 필요가 없는 문제입니다.

 

C - Rectangles (Code)

 

먼저 모든 사각형의 네 꼭짓점에 대해 x, y 좌표의 최대/최솟값을 각각 set 4개에 저장해두고, 필요에 따라 element를 제거하는 방식으로 해결할 수 있습니다. 많아봐야 1개가 제거되므로 굳이 set을 이용할 필요 없이 x,y 좌표의 최대/최솟값 각각을 최대 2개까지만 저장하는 방법도 있습니다.

 

D - Order Book (Code)

 

맨 처음에 문제를 읽을 때는 이해가 잘 안가 G로 넘어갔는데 G를 풀고나니 방향을 잡아서 급하게 짰습니다. 핵심 아이디어는 ACCEPT가 일어나는 순간 해당 ACCEPT는 BUY/SELL 2가지 가능성을 가지고 이전까지의 ADD들은 자동으로 BUY 주문인지 SELL 주문인지 결정납니다. 단 ACCEPT가 모순이 있는 경우는 별도로 체크를 해줘야합니다. 단, 끝나고 아직 미체결주문 N개가 남아있을 때 이들은 N+1가지의 가능성이 있으니 N+1을 곱해줘야합니다. 이 부분을 빠트려 정답을 받지 못했습니다.

 

G가 터져서 굉장히 많이 깎일줄 알았는데 다행히 A/B/C를 빨리 풀어서 선방한 것 같네요.