[AtCoder] AtCoder Beginner Contest 309

https://atcoder.jp/contests/abc309/tasks

Tasks - Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309)

요즘 앳코더 레이팅 좀 올려놓고 싶어서 계속 치고 있다.

이번 라운드도 어제 친 코포 라운드랑 비슷하게 마지막 한 문제 풀이는 나왔는데, 구현+케이스 하나 처리를 못해서 아쉬워서 적어본다. 풀이 떠올린 거에 만족한다. 이제 속도만 조금 올려보자.

 

A. 

(A-1)/3 < (B-1)/3 이면 Yes 아니면 No

 

B.

그냥 구현하면 된다.

시계 방향으로 돌아가니, 반시계 방향으로 채워주면 된다. 

 

C.

{a, b} 오름차순으로 정렬한 후에 순회하면서 (전체 b의 합)에서 각각의 b를 하나씩 빼주다가 k보다 작거나 같은 순간에 답을 출력하면 된다.

 

D.

1에서 BFS, N1+N2에서 BFS를 각각 돌리면, (1에서 거리 최댓값) + (N1+N2에서 거리 최댓값) + 1 이 답이 된다.

 

E.

'적어도 한 번' 보험에 들 수 있는지에 초점을 맞추면 답이 보인다.

각각의 정점에 해당 정점으로부터 보험에 들 수 있는 자손의 깊이 최댓값을 관리하면 된다.

일단 주어진 상황은 트리의 형태를 가지고 있으니, 루트부터 DFS를 돌면서 해당 값을 관리하면 된다. 

 

F. Upsolved

문제를 요약하자면, {a, b, c}이 여러 개가 주어지는 데, a_i < a_j && b_i < b_j && c_i < c_j를 만족하는 i, j 쌍이 있는 지를 묻는 문제이다. 이때 {a, b, c}는 서로 swap될 수 있다. 즉 3!의 가짓수가 가능하다.

 

https://www.acmicpc.net/problem/2336

2336번: 굉장한 학생

이 문제의 조건과 매우 비슷하다. 세그 스위핑을 하면 된다.

 

최솟값 세그먼트 트리를 관리하면 된다.

각각의 {a, b, c}에 대해서 3!의 가짓수를 모두 배열에 넣고, 오름차순으로 정렬한다. 

앞에서부터 순회하면서 [1, b] 쿼리 < c 이면 가능한 쌍이 있는 것이다.

 

놓치기 쉬운 포인트가 있는데, a가 같은 경우를 처리해야 한다. 나는 버퍼 느낌으로 a가 바뀔 때마다 세그먼트 트리를 update하는 식으로 구현했다.