AtCoder Beginner Contest 302

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

AGC는 무서워서 못 건들겠다

 

A. Attack

 

간단한 나눗셈 문제

 

B. Find snuke

 

문제를 잘못읽어 5분을 날렸다...

아무튼 브루트포스로 일일이 확인해주면 된다.

 

C. Almost equal

 

단순하게 S[i]와 S[j]가 서로 하나만 바꾸어서 같게 만들어질 수 있는지를 기록한 adj[i][j]를 만들면 된다.

이후 N = 8로 작기에 N!가지의 모든 경우에 대해서 해보면 된다.

 

D. Impartial Gift

 

전형적인 two pointer

B[j] <= A[i] + D인 최대의 j를 항상 구해주면 된다.

B[j] >= A[i] - D여야함에 유의

 

E. Isolation

 

우선 답 값을 ans라고 부르자.

그렇다면 ans 값은 ans값이 변화하는 순간만 확인해주면 된다.

즉, 2번 쿼리가 들어와서 한 정점이 isolate되거나 1번 쿼리에 의해 혼자 있던 정점이 연결되는지만 확인해주면 된다.

매번 N개를 모두 확인하지는 않고, 대충 간선의 개수만큼 확인을 하기에 시간 내에 답을 구할 수 있다.

 

우리는 흔히 정점들을 vector<vector<int>> adj로 관리한다.

하지만, 이렇게 관리할 경우 2번 쿼리에서 v - u라는 간선이 사라질 때,

adj[v]는 그냥 clear해버리기에 별로 상관 없지만, adj[u]에서 v를 제거하는 것이 까다롭다.

따라서 이 문제의 경우에는 adj를 vector<multiset<int>>로 관리하여 간선을 제거하면 된다.

 

F. Merge set

 

한 set의 원소들을 어떤 통로라고 생각할 수 있다.

예를 들어 서로 다른 두 SET인 A, B가 모두 어떤 원소 s를 가지고 있다면 A -> s -> B가 연결되었다 여길 수 있다.

따라서 S(i, 1), S(i, 2)... S(i, a)가 주어진다면, 이들이 모두 set(i) - number(S(i, j)) 간선을 의미한다고 여길 수 있다.

그렇다면 여기서 1부터 M까지의 최단경로를 구하면 된다.

 

G. Sort from 1 to 4

 

당연히 한 번의 swap으로 최대한 많은 원소들이 자신의 자리를 찾아가는 것이 이득이다.

아래의 swap들을 순서대로 해준다.

1. 당연히 자신이 나중에도 있을 자리에 있는 숫자는 swap에서 항상 제외된다.

2. 두 숫자가 서로의 자리에 존재한다면, 이 숫자를 서로 swap해준다. -> 1 swap 2개 자기 자리

3. 세 숫자가 서로의 자리에 존재한다면, 한 칸씩 밀어서 제자리를 찾는다. -> 2 swap 3개 자기 자리

4. 나머지는 4개가 서로 한칸씩 옮겨간다 -> 3 swap 4개 자기자리

(아래로 갈수록 효율 감소하기에 위쪽이 더 이득)

 

Ex. Ball Collector

 

사실 문제를 조금 스포당했다.

 

아무튼 자신의 조상노드들과 자신을 포함한 A값과 B값만 보면 된다.

예제 1처럼 (1, 2), (2, 3), (3, 1)이 있으면 한 칸씩 밀어가면서 (1, 2, 3)을 선택할 수 있음을 알 수 있다.

여기에 만약 (1, 3)이 하나 더 있으면 더 이상 서로 다른 숫자의 개수를 늘릴 수 없다.

즉 A - B간에 간선이 있다고 여긴다면, 모든 component에 대해서 min(V, E)의 합이 답이 된다.

따라서 항상 sum(min(V, E))의 합을 관리해주면 된다.

-> 이는 Union find로 할 수 있다.

 

다만 dfs 과정에서 자식 노드에 들어갔다가 올라오면 union find가 엉망이 되어서 올라온다.

따라서 union find를 복구해주는 과정이 필요하다.

정확히는 모르더라도 union find가 복잡도가 보장이 된다는 사실 정도는 모두가 안다.

즉, union find의 path compression 같은 과정이 일정 숫자를 넘지 않는다는 뜻이다.

따라서 복구하는 과정도 그냥 그대로 저장해서 그대로 진행하면, 계산량이 두 배가 되었을 뿐이니, 시간내에 할 수 있다.