AtCoder Beginner Contest 299

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

어차피 코드포스 점수가 더 높긴 한데 앳코더가 아파하는 것을 보니 가슴이 아프다

 

A. Treasure chest

 

bool in = false; 같은 것을 정의해서 '|'가 나오면 true로, 또 나오면 false로 바꿔준다.

그러면 '*'에서 true인지, false인지 확인하면 된다.

 

B. Trick Taking

 

단순하게 문제에서 하라는 것을 그대로 구현하면 된다.

 

C. Dango

 

Dango에서는 항상 L개의 ;o'가 연속하여 있음을 관찰할 수 있다.

따라서 끝에 '-'가 있는지만 확인해주면 최대 'o'의 개수와 크게 다를 바 없음을 알 수 있다.

 

D. Find by Query

 

흔한 이분탐색 interactive이다.

S[L] = 0, S[R] = 1로 유지하자.

그렇다면 S[mid] = 0이면 L = mid, S[mid] = 1이면 R = mid로 하면 된다.

언젠가 R - L = 1이 될 것이고 그러면 L이 답이 될 것이다.

 

E. Nearest Black Vertex

 

우선 N번 다익스트라를 돌려서 각 점간의 최소거리를 구하자.

그 후 예를 들어 i번 점에서 제일 가까운 black이 d라면, d보다 가까운 애들은 무조건 흰섹이란 뜻이므로 하얗게 칠한다.

이후 맨 마지막에 모든 점 j에 대해서 거리가 j인 black이 존재할 수 있는지만 확인해주면 된다.

 

F. Square Subsequence

 

참고로 이 문제가 G번보다 어렵다 (통계적으로)

사람들이 거의 무조건 F를 먼저 본다는 것을 고려한다면 G 솔브수가 F 솔브수보다 많다는 것은 큰 의미를 지닌다.

본인도 못 풀어서 jiangly의 풀이를 읽었다.

 

아무튼, 이 문제가 상당히 불편하다.

dp를 세우는데, T2의 맨 앞자리를 고려해주어야 하기 때문이다.

예를 들어 dp[i][j] = (현재 i번 자리, 그리고 j번자리를 차지하고 있는 TT의 수)라고 정의해보자

만약에 dp를 어떻게 잘 진행하다보면 T2의 첫 자리를 언젠가 지나칠텐데 이걸 알아서 멈추기가 쉽지 않기 때문이다

게다가 중복을 허용하지 않는 문제이기 때문에 중복도 제거해주어야 해서 불편하다.

 

nxt[idx][a] : idx보다 뒤에 있는 'a' 중에서 제일 앞에 있는 위치

-> nxt를 저장해두는 이유는 중복 제거를 위해서이다.

-> 원칙 : 즉 반드시 다음 char를 정할 때 바로 직후의 위치를 정해주어야 여러번 중복해서 세지 않는다.

 

불편함 때문에 T2의 첫자리를 정해주고 dp를 하자. (즉, T2의 첫자리는 i라고 하자)

그러면 우선 nxt[0][S[i]] < i여야 한다. (T2의 첫자리가 i이니, T1의 첫자리도 S[i]인데 i보다 있어야 한다)

dp[x][y] : (현재 x번 자리, 그리고 y번 자리를 차지하고 있는 TT의 수)라고 정의하자.

-> 그러면 맨 마지막에 nxt[x][s[i]] = i이면 ans에 더하면 된다. 

-> 현재 x번 자리와 y번 자리를 차지하고 있을 때, 위의 원칙대로 바로 직후에 i번 자리가 나와주어야 하기 때문이다.

아무튼, 현재의 TT 진행에서 다음에 문자 'a'가 온다고 생각하자.

그렇다면 아까의 원칙에 의해 x, y, 직후의 a를 선택하므로 pos1 = nxt[x + 1][a], pos2 = nxt[y + 1][a]이다.

-> 당연히 pos1 < i, pos2 < n이어야 진행이 가능하고, dp[pos1][pos2]에 dp[x][y]를 더하면 된다. 

https://atcoder.jp/contests/abc299/submissions/40906463

풀이에 워낙 기호가 많이 들어가서 구현과 함께 따라가면 이해할 수 있다.

 

 

G. Minimum Permutation

 

각 숫자가 마지막으로 등장하는 위치를 last[i]라고 하자.

그렇다면 last[i]의 최솟값보다 작거나 같은 위치에 있는 숫자는 맨 앞 숫자로 선택해도 상관없다.

즉, a[1] ~ a[min_last] 중에서 최솟값을 permutation의 맨 앞자리로 선택하는 것이 이득이라는 뜻이다.

그렇게 해서 x를 permuation의 맨 앞자리로 선택했다고 가정하자.

그러면 또다시 x를 제외한 last의 값들 중에서의 최솟값보다 작은 위치에 있는 숫자는 선택해도 괜찮다.

그러면 또다시 a[1] ~ a[min_last'] 중에서 x가 아닌 제일 작은 수를 구하면 된다.

 

이런식으로 숫자를 관리하려면 set을 쓰면된다.

last값들을 모두 s라는 set에 넣어두자.

pair({a[i], i})를 모두 t라는 set에 넣자.

만일 *s.begin() = y라면, t에는 {a[1], 1}, {a[2], 2}... {a[y], y}가 들어가 있을 것이다.

그러면 이제  t의 제일 앞에 있는 원소를 선택하면 된다.

{a[z] = x, z}를 선택했다고 하자. 

그러면 더 이상 x값은 필요가 없으므로 s에서 last[x]는 삭제하면 된다.

이제 위의 과정을 반복하면 된다.

*s.begin()은 계속해서 증가하므로 1번부터 모두 t에 넣는 과정을 반복하는 것이 아니라 y + 1번부터 y'까지 넣으면 된다.

 

Ex. Dice sum infinity

 

어렵지 않게 생각할 수 있는 점화식이

f[x] = (f[x - 1] + f[x - 2] + ... + f[x - 6]) / 6 + 1이다.

이 점을 이용해서 초항 6개 (f(1), f(2), f(3), f(4), f(5), f(6))으로 모든 f값들을 표현할 수 있다.

그러면 행렬제곱 같은거로 f(1e9-6) ~ f(1e9-1)을 f(1)~f(6)로 표현할 수 있다.

마지막에 x에 1~6을 대입해서 나온 식을 넣어서 이 숫자들을 구할 수 있다. 

사실 예제에서 f(1)이 주어진게 엄청 큰 힌트로 작용할거라 생각했는데 또 그렇지만도 않았다.

아싸리 예제에서 f(1)~f(6)을 주면 어땠을까도 싶었지만, 그렇다면 Ex가 아니였겠지..?