PS/오늘의 PS

오늘의 PS (16) - 220625

leo020630 2022. 6. 26. 03:14

ABC랑 코포 글로벌 라운드를 쳤다.

 

ABC 257

A. A to Z String 2 (0:01, +) *22

제한이 작아서 그냥 반복문으로 구현해줄 수 있다.

 

B. 1D Pawn (0:03, +) *91

역시 그냥 반복문으로 구현해주면 된다.

 

C. Robot Takahashi (0:07, +) *678

어른과 아이를 분류해서 정렬한 후, 각 값과 +-1을 대상으로 해 이분탐색으로 \(f(X)\)를 구해주면 된다.

 

D. Jumping Takahashi 2 (0:15, +) *1203

시간을 이분탐색으로 구한다고 가정하면, 그래프를 만드는 데에 \(O(N^2)\), 각 노드를 시작점으로 BFS를 하는 데에 \(O(N^2)\)이 걸려 \(O(N^2logX)\)에 문제를 해결할 수 있다.

 

E. Addition and Multiplication 2 (0:23, +) *1385

가장 싼 연산을 최대한 많이 써준 후, 남는 돈으로 앞 자리부터 보면서 최대한 키워주면 된다.

 

F. Teleporter (1:15, +3) *1775

우선 1과 N을 시작점으로 하고, 미확인 간선은 쓰지 않은 채로 BFS를 돌리자. 그 후 각 정점에 대해 간선을 연결해주는데, 이 때 정점들의 Level 변화를 잘 생각하면 문제를 해결할 수 있다. 나는 틀려서 계속 고치느라 코드가 좀 더럽다.

 

G는 좀 봤는데 문자열에 아직 익숙하지 않기도 하고 F때문에 멘탈이 온전치 않아 풀지 못했다.

Codeforces Global Round 21

A. NIT orz! (0:03, +)

z는 감소하기 때문에, orz중 가장 큰 값을 출력하면 된다.

 

B. NIT Destroys the Universe (0:07, +)

모두 0이면 0, 1번으로 되면 1, 그 이외에는 무조건 2번으로 가능하다.

 

C. Fishingprince Plays With Array (0:21, +2)

두 배열을 앞에서부터 보면서 합이 같아질 때 해당 구간에 있는 수들을 m으로 계속 나누었을 때 나머지가 같은지 확인해주면 된다. 예외처리를 제대로 안해서 두 번 틀렸다.

 

D. Permutation Graph (1:04, +4)

배열에서 앞으로 갈 수 있는 만큼 계속 가주면 되는데, 이를 관리하려면 최대-최소 세그를 쓰거나 set등으로 값을 관리해주면 된다. 나는 선형으로 하려다가 구현이 꼬여서 틀리기도 많이 틀리고 늦게 풀었다.

 

E. Placing Ninjas (1:19, +)

식을 정리하면 하키스틱 모양이 나온다. 선형으로 이항 계수를 구하는 방법을 알면 쉽게 해결할 수 있다.

 

페널티 관리만 잘 했어도 오렌지에 직빵으로 가는데, 앳코더와 코포 모두 페널티 때문에 망했다. 덕분에 화요일에 2086점으로 Div.2를 치게 되었다. 제출할 때 1분은 생각하고 제출하는 습관을 기르자.

'PS > 오늘의 PS' 카테고리의 다른 글

오늘의 PS (18) - 220629  (0) 2022.06.30
오늘의 PS (17) - 220627  (0) 2022.06.28
오늘의 PS (15) - 220621~22  (0) 2022.06.23
오늘의 PS (14) - 220620  (0) 2022.06.21
오늘의 PS (13) - 220619  (0) 2022.06.20