AtCoder Beginner Contest 301

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

 

가볍게 풀고 딴거 하려고 했는데 꽤(너무) 매웠다.

F가 이번에 83솔로 어마어마하게 강력했다.

G도 구현이 상당히 개더러워보이고 EX도 살짝 그런 느낌이다

 

A. Overall Winner

 

단순히 승리 횟수를 세면 된다.

 

B. Fill the Gaps

 

a[i]와 a[i + 1] 사이에 있는 모든 수를 추가로 출력해주면 된다.

 

C. AtCoder Cards

 

우선 겹치는 'a'~'z'는 모두 제거하자.

그 다음에 atcoder에 포함되는 애들은 존재하는 @로 채워넣어주면 된다.

이후에도 여전히 다른 단어가 존재한다면 No

 

D. Bitmask

 

우선 ?를 모두 0으로 취급하여 최소숫자를 구하자.

이후 앞 자리부터 1로 바꾸어도 가능하다면 바꾸는 식으로 숫자를 늘리면 된다.

 

E. Pac-Takahashi

 

문제 상황에서 바로 비트 dp를 하면 좋겠지만 안타깝게도 그러면 H * W * (1 << 18)이라 너무 느리다.

따라서 우선 S, G, o 들의 서로 간의 거리를 모두 구한다.

이후 S, G, o들에 한해서만 거리에 대한 비트 DP를 진행하면 된다.

그러면 복잡도가 20 * (1 << 20) 정도로 시간이 단축된다.

 

F. Anti-DDoS

 

이런 것은 항상 안 겹치도록 세는 것이 중요하다.

즉 어떠한 조건을 만족시키는 경우들을 분리해서 세어주면 된다.

다음과 같은 방법으로 분리하여 계산하였다.

a[i] = (i번째 자리에서 최초로 같은 대문자가 두 번 반복되는 경우의 수)

b[i] = (i번째 자리에서 최초로 같은 대문자 반복 후 소문자가 나오는 경우의 수)

-> 각 문자열은 대문자가 두 번 나오는 시점이나 처음으로 소문자가 나오는 시점이 유일하기에 중복하지 않게 셀 수 있다.

 

우선 a[i]를 구해보자.

chk를 현재까지 등장하지 않은 대문자의 개수라고 하자

1) S[i] = '?'인 경우

-> ...A....?로 현재 물음표가 이미 등장한 대문자와 대응되어 처음으로 대문자가 두 번 반복될 수 있다

    -> 지금까지 물음표가 qs개 있었다고 가정하자.

    -> 그렇다면 물음표들은 현재 등장하지 않은 chk개의 대문자들은 최대 한 번씩 사용할 수 있다.

    -> 물음표들이 사용한 대문자의 수가 j라면 a[i] = sum( 26^(qs - j) * C(qs, j) * C(chk, j) * j! )이 된다.

    -> 나머지 경우들도 비슷한 방식으로 구할 수 있다.

-> ....?....?로 물음표 두 개가 chk에 포함된 대문자와 대응되어 처음으로 대문자가 두 번 반복될 수 있다.

2) S[i] = 'A'인 경우

-> ...?...A로 물음표 하나가 A에 대응되어 대문자가 두 번 반복될 수 있다.

-> ...A...A로 A가 두 번 반복될 수도 있다. 또한 이것이 발생하면 a[i + 1], a[i + 2], ... = 0임을 알 수 있다.

 

b[i]를 구하자.

우선 기본적으로 i보다 앞에서 DD가 나오는 경우의 수인 a[x] 값의 합을 의미하는 j라는 숫자를 따로 들고 다니자.

j는 좀 더 자세히 설명하자면 i 이전의 숫자들(i > x)에 대해서 a[x] * 26^ - (x까지 물음표의 개수)의 합을 의미한다.

1) S[i] = 'a'

-> 사이의 물음표들은 모두 대문자였어야 하므로 j * 26 ^ (i까지 물음표의 개수)가 된다.

-> 지금보다 앞에서 DD가 나왔다면 전부 여기서 소문자가 등장했으니 j = 0 처리를 해준다.

2) S[i] = '?'

-> 여기의 물음표는 반드시 소문자, 앞의 물음표들은 대문자여야 하니 j * 26 ^ (i번째를 포함한 물음표의 개수)가 된다.

b[i]는 a[i] 뒤에 소문자가 하나 나오면 끝이고, 답은 b[i] 뒤에 대문자가 하나 나오면 끝이니 답은 비슷하게 구할 수 있다.

 

Editorial 상의 풀이가 사실 처음에 생각했던 풀이와 더 가깝다.

기본적으로 dp를 할 때 우리는 state를 생각한다.

다음과 같이 state를 정의하자 : 대문자가 0~26종류, DD 이후 소문자 없음, DD 이후 소문자 있음

-> 이렇게 29개짜리를 이용하여 dp를 굴릴 수 있다.

-> 어차피 맨 처음 string에서 모든 문자들이 정해져 있기 때문에 이런 dp가 가능하다.

 

밑은 구현하진 않았지만 풀이가 할만하다.

 

G. Worst picture

 

어차피 최선이 되는 점은 주어진 점들을 잇는 두 직선의 교점중 하나가 될 것이다.

따라서 n^4개의 교점 중에서 답이 반드시 존재하고, 이 교점들 하나하나를 n^2 시간으로 검증하면 된다.

물론 아마도 n^4개의 교점을 찾는 과정에서 얻은 정보를 이용하면 n^5 정도의 시간으로 될 것 같다.

의외로 답지나 jiangly의 코드 등을 보면 간단하다.

 

Ex. Difference of Distance

 

1차적으로 A[j]의 weight가 d(s, t)와 같아야 한다.

-> 우선 d(s, t)는 크루스칼의 공(#1396)의 방법으로 모두 구할 수 있다.

사실 알고보니 같기만 한지 판정하면 되는지라 PBS까지 안 가도 된다.

-> Weight에 대해 정렬하고 UF의 merge를 하는데, merge 전에는 연결 안되었고, merge 후에 연결되는지 확인.

 

1차적인 검증을 거치고 나면, A[j]가 없더라도 s, t가 연결되어 있는지를 확인해주면 된다.

이 과정은 A[j]와 같은 weight를 가진 간선들에 대해서 확인을 해주면 된다.

-> 이 간선들을 이용해서 SCC를 만든 다음에, A[j]가 포함된 loop이 있는지 확인해주면 된다.

-> 만약 있으면 A[j]가 사라져도 s, t를 여전히 이을 수 있고, 없다면 s, t는 이어지지 못한다.