AtCoder Beginner Contest 349

 

시험도 끝났겠다 앳코더 계정을 옐로로 올려놓기 위해 ABC를 쳤다.

 

A. Zero Sum Game (0:01, +) *

제목에 풀이가 써 있다. Zero Sum Game이므로 -(주어지는 수의 합)을 출력하자.

 

B. Commencement (0:03, +) *

시키는 대로 구현해주면 된다.

 

C. Airport Code (0:09, +2) *

앞에서부터 \(T\)의 각 문자가 등장할 때마다 그리디하게 골라주면 된다. 코딩을 절어서 2번 틀렸다.

 

D. Divide Interval (0:15, +) *

정확한 증명은 모르겠지만 왠지 그래야 할 것 같은 코드를 짜서 맞았다. 갈 수 있는 한 최대로 계속 가주면 된다.

 

E. Weighted Tic-Tac-Toe (0:27, +1) *

일단 게임이고, 제한을 보면 \(3^9\) 게임 DP를 하라는 것을 알 수 있다. 귀찮음을 참고 열심히 구현해주면 된다. int를 써서 한 번 틀렸다.

 

F. Subsequence LCM (0:53, +) *

비슷한 문제를 생각해 본 적이 있어서 빨리 풀었다. 먼저 \(A\)에서 원소들을 고를 때에는, \(M\)에 없는 소인수가 있거나 \(M\)에 있는 소인수가 더 많이 있는 경우 고려하지 않아도 된다. 이렇게 원소들을 남기면 소인수가 몇 개 있냐는 중요하지 않고 각 소인수가 \(M\)과 같은 개수만큼 있는지 여부만이 중요해진다. 따라서 각 수의 상태를 \(2^p\)개로 표현할 수 있다. 계산을 해 보면 제한 안에서 \(M\)의 서로 다른 소인수 개수는 최대 13개이다. 이후는 이를 이용해 or knapsack 비슷한 bit DP를 돌려 주면 된다. 시간 복잡도는 \(O(4^p)\)이다. \(M\)이 1인 경우만 유의해서 처리해주자.

 

G. Palindrome Construction (1:21, +2) *

문제에서 주는 배열은 Manacher 알고리즘이 구하는 그것과 동일하다. 당연히 연관이 없을 수는 없으므로 Manacher 알고리즘의 동작 원리를 잘 생각해보자. 똑같이 진행하되, \(i \le r\)일 때에는 불가능한 경우를 처리해주어야 하는 대신 배열은 미리 구한 것을 이용해 잘 채워줄 수 있다. \(i > r = i-1\)일 때에는 \(i\)번째 칸에 사용할 수를 정해야 하는데, 처음에는 1 혹은 2로 가능하다고 생각해서 제출했지만 틀렸다. 잘 생각해보니 해당 칸에 끝나는 팰린드롬을 깨기 위해 사용해야 하는 수를 set등에 저장해줄 수 있고, mex를 같이 관리해주면 적절한 수를 정해줄 수 있다. 그렇게 냈는데 케이스 2개에서 틀려서 반례를 열심히 찾아본 결과,0 1 1 1 0 에 Yes를 출력하고 있었다. Manacher를 한 번 더 돌려서 실제 만든 배열에서 구한 \(A\)값과 주어진 값을 비교했더니 예제가 잘 나왔고, 제출해서 맞았다.

 

좀 찍으면서 하긴 했지만 G를 빠르게 푼 덕에 Rated 2등을 찍으며 옐로로 승급할 수 있었다.ABC는 사실 큰 관심사가 아니고.. ARC나 열심히 연습해보자.