Codeforces(618): Wunder Fund Round 2016 후기

이번 라운드는 상품이 꽤 화려했다.

• 1 place — PlayStation 4
• 2 place — Xbox One
• 3-5 places — Sega MegaDrive 16bit with games
• 1-50 places — Wunder Fund T-Shirts!
• 51-500 places — 50 T-Shirts to random participants!

꽤 많은 참가자들이 참가했고, 라운드 시작 시 서버가 힘들어해서 시작이 5분 지연되기도 했다.

---

A. Slime Combining

\(x\) 슬라임은 \(1\) 슬라임이 총 \(2^{(x-1)}\)개 뭉쳐져 생긴 것이다.
귀납적인 생각을 통해, \(n\)에 \(2^x\) 비트가 켜져 있다면, \(x+1\) 슬라임이 존재하고, 모든 슬라임들은 내림차순으로 있을 것이다.

본인 소스

---

B. Guess the Permutation

\(min\)의 성질을 생각해본다면, \(0\) 혹은 \(1\)만 존재하는 행과 열이 있다면, 그 위치의 순열에는 반드시 \(1\)이 들어가 있을 것이다.
그렇다면 그 위치에 답을 기록하고, 모든 테이블에서 그 행과 열을 제외해본다.
또다시 \(min\)의 성질을 생각해본다면, \(0\) 혹은 \(2\)만 존재하는 행과 열을 찾으면 될 것이다.
이런 식으로 반복하며 답을 기록하면 된다.
총 \(N\)번 답을 기록할 것이고, 그 때마다 \(O(N^{2})\)의 시간이 소요되므로 전체 시간복잡도는 \(O(N^{3})\).

본인 소스. 여기서는 행렬의 모든 원소를 \(1\)씩 감소시키는 방법을 사용했다.

---

C. Constellation

\(x\)좌표가 가장 작은, 만약 같다면 \(y\)좌표가 가장 작은 순서대로 두 개의 점 \(p\)와 \(q\)을 잡아보자.
그리고 \(\overleftrightarrow{pq}\) 위에 있지 않은 점 중 \(x\)좌표가 가장 작은 점 \(r\)을 잡아보자. (주어진 조건에 의해 항상 존재)
\(p\), \(q\), \(r\)을 제외한 주어진 점들 중, \(\triangle pqr\)의 안에 점이 있으려면 \(x\)좌표가 \(r\)보다 작아야 하고, 또한 \(\overline{pq}\) 위에 있지 않아야 하므로, \(r\)을 잡는 방법과 모순된다.
따라서 \(p\), \(q\), \(r\)을 출력하면 된다.

본인 소스

---

E. Robot Arm

점들 중 임의의 구간에 대해 어떤 점에 대한 회전 혹은 어떤 방향으로의 평행이동을 수행해야 하는 문제였다.
평행이동만 있다면 X축과 Y축을 분리하여 각각 구간을 갱신해주면 되나, 회전이동을 하려면?
즉, 회전이동을 하는 기준점을 찾을 수 있어야 하고, '점들에 대해 회전이동을 수행한다'라는 쿼리를 구간에 대해 갱신할 수 있어야 한다.
회전이동의 시작점이 고정되어있다면, 점들을 크기가 2인 열벡터로 잡고, 2차원 행렬로 이루어진 세그먼트 트리에 lazy propagation을 적용할 수 있겠다.
시작점이 고정되어있지 않다면, 평행이동과 회전이동을 수행할 수 있기 위해서 뭔가 특별한 것을 써야 할까?

바로 3차원 벡터를 쓸 수 있다.
모든 점의 열벡터에 1이라는 값을 추가하여, 점을 \(3 \times 1\) 열벡터로 생각하자.
$$\left(\begin{matrix}x\\y\\1 \end{matrix}\right)$$
점을 \((p,q)\)만큼 평행이동시키는 행렬은 다음과 같다.
$$\left(\begin{matrix}1&0&p \\ 0&1&q \\ 0&0&1 \end{matrix} \right)$$
점을 원점을 기준으로 시계방향으로 \(\theta\)만큼 회전시키는 행렬은 다음과 같다.
$$\left(\begin{matrix} \cos \theta& \sin \theta& 0 \\ -\sin \theta & \cos \theta & 0 \\ 0&0&1 \end{matrix} \right)$$
따라서, 특정 점 \((p,q)\)을 기준으로 시계방향으로 \(\theta\)만큼 회전시키는 행렬은 다음과 같다.
$$\left(\begin{matrix}1&0&p \\ 0&1&q \\ 0&0&1 \end{matrix} \right) \left(\begin{matrix} \cos \theta& \sin \theta& 0 \\ -\sin \theta & \cos \theta & 0 \\ 0&0&1 \end{matrix} \right) \left(\begin{matrix}1&0&-p \\ 0&1&-q \\ 0&0&1 \end{matrix} \right) $$

본인 소스. 열벡터 구조체 v3와 행렬 구조체 m3를 눈여겨보라. getPoint 함수는 루트에서 해당 점까지 내려가며 lazy propagation을 적용시켜서, data에 실제 그 점의 좌표가 저장되게 한다.