AtCoder Beginner Contest 210 후기

AtCoder Beginner Contest 210

---

C. Colorful Candies

길이가 \(K\)인 구간을 투 포인터로 관리하면서 양 끝에서 새로운 수가 추가되는지, 사라지는지를 확인하면 된다.

 

D. National Railway

두 지점을 고르는 것은 두 가지 경우가 있다.
1) 왼쪽 위와 오른쪽 아래 (\(i\le i',\ j\le j'\))
2) 오른쪽 위와 왼쪽 아래 (\(i\le i' \ j\ge j'\))

1)의 경우는 \(A_{i,j}+A_{i',j'}+(i'-i)+(j'-j)\)이다.

연관된 것끼리 묶으면, \((A_{i,j}-i-j)+(A_{i',j'}+i'+j')\)이 되므로, 오른쪽 아래 점이 \((i',j')\)가 되는 경우의 최솟값은 \(i\le i',\ j\le j'\)인 점들 중 \(A_{i,j}-i-j\)의 최솟값으로 구할 수 있다. 그리고 이 최솟값은 Prefix Sum으로 구할 수 있다.

2)의 경우도 같은 방법으로 할 수 있다.

 

E. Ring MST

문제 제목에도 써 있듯이, MST와 같이 가중치가 작은 간선부터, 트리가 되도록(사이클이 생기지 않도록) 간선을 추가하면 된다.

하지만 정점과 간선이 매우 많기 때문에 일반적인 MST 알고리즘으로는 풀 수는 없는데, 사이클이 생기지 않도록 간선을 최대한 추가한다면 컴포넌트가 어떻게 나뉘는지를 확인해야 한다.

결론적으로는, \(\{0,\ A_i,\ 2A_i,\ \cdots\},\ \{1,\ 1+A_i,\ 1+2A_i,\ \cdots\},\ \cdots ,\ \{\gcd(N,A_i)-1,\ \gcd(N,A_i)-1+A_i,\ \gcd(N,A_i)-1+2A_i,\ \cdots\}\)으로 컴포넌트가 나뉜다.

이후에는 \(0,\ 1,\ \cdots ,\ \gcd(N,A_i)-1\)을 한 컴포넌트로 합쳐야 하는 것과 같으므로 \(N\)을 \(\gcd(N,A_i)\)로 바꾼 뒤에 진행하면 된다.

 

F. Coprime Solitaire

각 카드마다 앞면, 뒷면 둘 중 하나를 정해줘야 한다. \(x_i\)가 앞면, \(\neg x_i\)가 뒷면이 되도록 정하고, 2-SAT으로 풀 수 있다.

소인수를 구해서 같이 보이면 안 되는 카드들의 집합을 구할 수 있다. 예를 들면, \(2\)의 배수인 집합, \(3\)의 배수인 집합 등을 구한다.

이러한 집합에 있는 것들 중에서는 한 개 이하만 선택될 수 있다. 즉, 집합 안에 있는 변수들 중에서 한 개 이하만 참이 된다.
한 개 이하만 참이 되도록 하는 것은 새로운 변수를 만들어서 Prefix Sum을 구하듯이 할 수 있다. (링크) (비슷한 문제)

이후에는 SCC로 가능한지 확인하면 된다.

 

---

지금까지 중에서 제일 좋은 퍼포먼스가 나와서 후기를 썼다. 내가 느끼기에는, 핵심인 D와 E가 복잡해보이지만 풀이가 정리되고 나면 굉장히 깔끔해지는 재밌는 문제였다. F는 2-SAT으로 푼다는 아이디어는 재밌었지만 소인수분해도 들어가고 추가적인 테크닉도 필요해서 어쩔 수 없이 과하게 높은 난이도를 받은 것 같다.

D는 실수를 해서 한 번 틀렸고, F는 아주 큰 실수를 한 코드를 제출했는데 답이 Yes 또는 No인 문제여서 WA가 몇 개 안나오는걸 보고 배열 크기만 늘리고 다시 제출해서 2번 틀렸다.

ABC는 최대 퍼포먼스가 2400이여서 레이팅이 그렇게 많이 오르지는 않았다. 100점 정도는 오를거라고 생각했는데 60점이 올라서 결국 1단은 못 갔다.

끝나고 흐름 타서 코드포스도 했는데 완전히 망했다.