Codeforces Round 859 (Div. 4)

Dashboard - Codeforces Round 859 (Div. 4) - Codeforces

 

C

010101010101로 치환되는지만 확인하면 된다. 즉,

1. 홀수번째 index가 모두 1로 치환될 수 있는지
2. 짝수번째 index가 모두 0로 치환될 수 있는지
3. 그러면서 치환 과정에 모순이 생기지 않는지 확인하면 된다.
(101010 이 되는지 추가적인 확인은 불필요 !)

 

F

많이 귀찮은 구현 문제.

유한번의 bounce 만으로 시행이 끝난다고 하자. 그러면 각 벽면 (r, c)에서 bounce는 많아야 2번이다.
그 부분은 cnt라는 map을 통해서 관리한다.

다음과 같은 알고리즘을 이용한다.
가. 현재 상태(cr, cc, dr, dc)에서 다음 벽을 튕기고 나온 상태(nr, nc, ndr, ndc)를 구한다.
나. 만약 (cr, cc) 와 (nr, nc) 사이에 도착지점 (ER, EC)이 존재한다면 그동안의 bounce 횟수를 return
그렇지 않다면 (가)로 돌아간다.

 

핵심이 되는 get_cnt() 는 다음과 같다.
공의 행으로의 이동과 열의 이동을 따로 생각하자. 현재 상태에서 다음에 벽에 튕기기까지 이동하는 칸의 수는 
min(벽을 부딪히기 전까지 행의 수, 벽을 부딪히기 전까지 열의 수)이다. 이를 delta라고 한다면
공이 벽에 부딪히는 위치 next row(nr), next column(nc)는 다음과 같다.
nr := cr + dr*delta
nc := cc + dc*delta (dr, dc는 방향에 따라 1이나 -1이다)

한편, 기존의 방향정보 dr, dc와 벽에 부딪히는 위치를 이용하여 벽을 튕기고 방향변화를 구해주면 된다.

 (cr, cc) 와 (nr, nc) 를 잇는 선분에 도착지점 (ER, EC)이 존재하는지 판단하는  include() 는 다음 두 가지를 보이면 된다
1.두 벡터  (cr, cc) - (ER, EC) 와 (nr, nc) - (ER, EC)가 평행하다
2. cr 과 nr 사이에 ER가 있고 cc과 nc 사이에 EC가 있다.

 

G1 + G2

배열 [1] 부터 배열의 원소를 추가해가며 연산을 통해 표현할 수 있는 값의 범위를 생각하자.
초기에는 범위 [0, 1] 의 정수를 표현할 수 있다. 따라서 두번째로 배열에 추가할 수 있는 원소는 1이다.

1이 추가되면 배열 [1, 1] 로 표현할 수 있는 값의 범위는 [0, 2] 이다. 두번째로 원소 2를 추가했다고 하자.
배열 [1, 1, 2] 로 표현할 수 있는 값의 범위는 [0, 4]이다.
i) 2를 포함하지 않고 배열 [1, 1, 2] 으로 표현할 수 있는 범위가 [0, 2] 이고
ii) 2를 반드시 포함하면서 배열 [1, 1, 2] 으로 표현할 수 있는 범위가 [2, 4] 이기 때문이다.

배열 A로 표현할 수 있는 값의 범위가 [0, r]이라고 하자. 이때 원소 a ∈ [0, r] 를 추가했다고 하자.
배열 A∪{a} 로 표현할 수 있는 값의 범위는 [0, r+a]이다.
i) a를 포함하지 않고 배열 A∪{a} 으로 표현할 수 있는 범위가 [0, r] 이고
ii) a를 반드시 포함하면서 배열 A∪{a} 으로 표현할 수 있는 범위가 [a, a+r] 이기 때문이다.