AtCoder Beginner Contest 349

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

가벼운 마음으로 참가했는데 굉장히 초조하게 풀었다.

간신히 4초를 남기고 올솔을 한 모습이다.

 

A. Zero Sum Game

 

문제 이름 자체가 힌트다.

제로섬 게임이므로 -(나머지의 합)이 답이 된다.

 

B. Commencement

 

문제 그대로를 해보면 된다.

우선 모든 글자에 대해 cnt[x] = (S에 등장하는 횟수)를 구하고, 이 값이 모두 0이나 2인지 확인하면 된다.

 

C. Airport Code

 

우선 pos[x] = {y | S[y] = x}를 구하자.

그러면 각각의 조건에 대해 체크하면 되는데..

1) pos[T[0]][0] < x < pos[T[2]].back()이 성립하도록 하는 x가 pos[T[1]]에 존재하는가?

-> upper_bound(pos[T[0]][0])가 pos[T[2]].back()보다 작은지 확인하면 된다.

2) pos[T[0]][0] < pos[T[1]].back()이 성립하고 T[2] = 'X'

 

D. Divide Interval

 

바텀업 세그를 했다면 특히나 쉽게 구현할 수 있는 부분이라 생각한다.

아무튼 i = 1, 2, 4, 8, ...  순서대로 (단, L >= R이 되면 break)

1) (L & i)이 성립한다면 [L, L + i)를 삽입하고 L += i

2) (R & i)이 성립한다면 [R - i, R)를 삽입하고 R -= i

이 구간들을 정렬한 뒤 출력하면 된다.

 

E. Weighted Tic-Tac-Toe

 

개빡구현 1.

일단 모든 보드의 상태는 3^9가지 경우이다.

현재 문제 조건상에서 보드의 상태가 주어진다면 승패는 즉시 정해진다.

따라서 이 모든 3^9가지 상태에 대해서 승패를 미리 구해보면 된다.

상태 S1 자체가 승리가 될 수 있고 (S1이 한 줄의 같은 색이 존재하거나, 흰 칸이 없고 더 합이 큰 경우)

S1에서 넘어갈 수 있는, 패배인 S2가 존재하면서 S1이 있을 수 있다.

여러 사람의 구현을 참고하자.

 

F. Subsequence LCM

 

LCM을 M으로 만드는데 중요한 숫자들은 한정되어 있다.

생각해보면 M = 12라고 한다면, 여기에 2가 포함될지 말지는 1이 포함될지 말지와 같다.

결국 2로는 부족하고 4의 배수부터 포함되는게 유의미하다.

 

M = p1^q1 * p2^q2 * ... 이라고 가정하자.

그렇다면 숫자들을 다음과 같이 비트마스킹하자

-> X를 Y에 대응한다면, Y의 i번째 비트가 켜져있다면 X는 p[i] ^ q[i]의 배수이다.

-> cnt[Y] = (비트마스킹한 값이 Y가 되면서 동시에 M의 약수인 A의 원소의 개수)

 

그러면 DP[X][Y] = (값이 X 이하인 수들로 만든 집합 중 LCM이 Y인 경우의 수)라고 하자.

1) x + 1을 집합에 포함시킬 경우 : dp[x + 1][y | (x + 1)] += dp[x][y] * (pow(2, cnt[x + 1]) - 1)

2) x + 1을 집합에 포함시키지 않을 경우 : dp[x + 1][y] += dp[x][y]

소수의 개수를 sz라 한다면, X, Y 모두 1 << sz 미만이고 O(1 << (2sz))로 구할 수 있다.

M은 10^16 이하이기에 sz는 그렇게 크지 않다. 

 

이건 SOS dp 비슷하게도 가능하다.

다만, 일반적인 SOS dp는 간단하게 (y in x인 모든 cnt[y] 값의 합)이지만, 여기서는 포함과 배제를 해야한다.

그래서 조금 형태가 다르게 transformation이 이루어진다.

 

G. Palindrome Construction

 

문제는 3가지 부분으로 쪼갤 수 있다.

1) 모든 i에 대해서 (i - 1, i + 1), (i - 2, i + 2), ..  (i - a[i], i + a[i])가 같도록 만들어주기

2) 모든 i에 대해서 (i - a[i] - 1)과 (i + a[i] + 1)이 달라질 수 있는지 확인하기

3) Lexicographically smallest로 만들기

 

'같도록 만들기'는 역시나 union find로 한다.

그러면 아주 쉽게 2)도 해결할 수 있다. find(i - a[i] - 1)과 find(i + a[i] + 1)이 다르게 해주면 되기 때문이다.

3)도 사실 별로 어렵지 않다.

앞에서부터 출력한다고 생각하자. (i = 0 ~ N - 1)

i번째 원소를 출력할 때에는 2)의 조건들을 만족하는 선에서 최솟값을 출력해주면 된다.

a) find(i') = find(i)가 성립하는 i' < i가 존재한다면, i'에서 출력한 값(= print[find(i)])을 그대로 출력한다.

b) 그런 적이 없다면 2)의 조건상 find(i) != x인 모든 x와 겹치지 않는 값이 될 때까지 print[find(i)]++를 해준다.

-> 이것은 find(i) != x인 모든 x의 print[x] 값을 set에 넣어두는 방법으로 할 수 있다.

 

하지만 1)에서 모든 i에 대해서 (i - 1, i + 1), (i - 2, i + 2), ..  (i - a[i], i + a[i])를 merge하는 것은 너무 느리다.

우리는 사실 이와 비슷한 것을 본 적이 있는데, 바로 Manacher algorithm에서 이다.

따라서 manacher algorithm을 하듯이 짜주면 된다.

근데 나는 이걸로 의문의 TLE를 받아서 어거지로 다음과 같은 조건문으로 통과시켰다.

Manacher은 실제 가능한 S에서 돌리지만, 여기의 a값에 대응되는 S는 존재하지 않을 수 있음을 생각해야 한다.

즉 Manacher의 복잡도는 보장이 되지만, 여기서는 보장이 되지 않는 경우가 발생하는 듯하다.

 

개빠르게 for문을 돌아서 저 부분을 무사통과 (다음 코드를 확인하라)

불가능한지 확인하는 조건을 미리 걸어두는 것으로 해결할 수 있다. (아래와 같은 형태로 하면 된다)

 

의문의 자료구조인 Range Parallel union find로 풀 수 있다고 한다.

그냥 저 자료구조 자체가 (L, R) (L - 1, R + 1), ... (L - dist, R + dist)의 union을 지원한다고 한다.