오늘의 PS (6) - 220508

ABC와 코포 Div. 1이 있어서 둘다 쳤다.

 

AtCoder Beginner Contest 250

A. Adjacent Squares (0:01, +) *25

if문을 4개 써주면 된다.

 

B. Enlarged Checker Board (0:04, +) *109

그냥 별 찍기다.

 

C. Adjacent Swaps (0:07, +) *517

값을 담은 배열과 역추적 배열을 만들어서 잘 바꿔주면 된다.

 

D. 250-like number (0:16, +) *797

우선 에라토스테네스의 체로 \(10^6\) 이하의 소수를 모두 구해준 후, 각 소수에 대해 이분탐색으로 만족하는 더 작은 소수의 개수를 구해주면 된다.

 

E. Prefix Equality (0:23, +) *1421

\(C_i\)를 \(A_i\)가 \(B\)에서 가장 처음으로 등장하는 위치, \(D_i\)를 \(B_i\)가 \(A\)에서 처음으로 등장하는 위치로 정의하자. 등장하지 않을 시 INF값으로 정의한다. 그러면 주어지는 쿼리가 yes임은 \(max(C_1..C_x)<=y\)이며 \(max(D_1..D_y)<=x\) 임과 동치이다. 

 

F. One Fourth (1:13, +2) *2044

풀이는 간단하다. 각 정점에 대해 넓이로 이분탐색을 돌려서 넓이/4에 가장 가까운 넓이를 찾으면 되는데 구현 미스로 인해 시간을 너무 많이 썼다. 기하 구현 속도가 많이 느린 것 같다. 연습해야지..

 

Codeforces Round #789 (Div. 1)

A. Tokitsukaze and Strange Inequality (0:05, +)

b, c를 고정한 후 누적합 배열로 가능한 a, d의 개수를 체크하면 된다.

 

B. Tokitsukaze and Meeting (1:16, +)

열은 쉽게 관리할 수 있는데, 행이 문제다. 최근 \(M\)개에 대한 누적합을 들고 있으면 첫 행의 만족 여부는 알 수 있다. 다음 행부터의 개수는 DP를 이용해 \(M\)턴 전의 상태를 불러오면 된다. 어려운 문제는 아닌데, C를 잡다 와서 솔브 시간이 많이 늦었다.

 

C. Tokitsukaze and Two Colorful Tapes (1:51, +1)

우선 주어진 배열을 Permutation Cycle으로 분리해야 됨은 쉽게 알 수 있는데, 그 뒤로가 막막하다. 뭔가 찍어서 맞춰야 할 것 같은데, 찍은 규칙들이 다 틀려서 종료 직전에야 겨우 맞았다. 답은 각 사이클에 대해 \(floor(L/2)\)를 모두 더해준 후, 그 횟수 만큼 길이 2인 사이클을 만든다고 생각하면 된다. 이런걸 다들 어떻게 빨리 생각하지?

 

앳코더는 계속 오르는데 사이트 특성상 속도가 그렇게 빠르지 않은 것 같아 문제고, 코포는 오렌지만 가면 너무 빨리 떨어지는 것 같아 문제다. 이번엔 겨우 생존하긴 했는데.. Div. 1 버츄얼을 돌려야 하는지 고민이다.