AtCoder Beginner Contest 246

 

앳코더는 레이팅이 잘 오르는 것 같다. 아직 낮아서 그런가?

 

A. Four Prints (0:01, +) *28

직사각형의 세 꼭짓점이 주어졌을 때 남은 하나의 점을 구하면 된다. 적당히 if문을 써주면 구현할 수 있다. A번치고 오래 걸렸다.

 

B. Get Closer (0:03, +) *79

구하라는 것을 계산하면 된다. 문제에서 제한을 상당히 편하게 주어 대충 짜도 된다.

 

C. Coupon (0:07, +) *336

\(A_{i}/X\)의 합과 \(K\)를 잘 비교해 처리해주면 된다.

 

D. 2-variable Function (0:30, +3) *1148

\(A\)를 고정한 후 \(B\)는 이분 탐색으로 찾아주면 된다. 최대 \(10^6\)까지 돌리면 되니 오버플로우는 고려할 필요가 없으며, 예외처리가 조금 필요하다.

 

F. typewriter (0:42, +) *1677

식이 쉽게 나오기 때문에 적당히 포함배제를 돌려주면 된다. 포함배제에 익숙하다면 아마도 굉장히 빨리 풀이를 찾을 수 있을 것이다.

 

E. Bishop 2 (0:57, +) *1476

얼핏 보면 \(O(N^3)\) 같으나, state에 방향을 추가해주면 \(O(4N^2)\)개의 상태로 표현할 수 있다. 가중치가 0 혹은 1이므로 0-1 BFS를 사용하면 \(O(N^2)\)에 해결할 수 있다.